COMMENT ⊗   VALID 00027 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	\input acphdr % Answer pages (double-check position of figures)
C00004 00003	% Page 562
C00008 00004	% Vicinity of page 562
C00028 00005	% Vicinity of page 565
C00045 00006	% Vicinity of page 568
C00050 00007	% Vicinity of page 569
C00056 00008	% Vicinity of page 570
C00069 00009	% Vicinity of page 572
C00082 00010	% Vicinity of page 574
C00091 00011	% Vicinity of page 575
C00110 00012	% Vicinity of page 579
C00124 00013	% Vicinity of page 582
C00135 00014	% Vicinity of page 584
C00140 00015	% Vicinity of page 585
C00151 00016	% Vicinity of page 587
C00163 00017	% Vicinity of page 589
C00174 00018	% Vicinity of page 591
C00181 00019	% Vicinity of page 592
C00190 00020	% Vicinity of page 593
C00199 00021	% Vicinity of page 595
C00213 00022	% Vicinity of page 597
C00223 00023	% Vicinity of page 599
C00228 00024	% Vicinity of page 600
C00241 00025	% Vicinity of page 602
C00252 00026	% Vicinity of page 604
C00278 00027	\end % be sure this comes at an opportune time!
C00279 ENDMK
C⊗;
\input acphdr % Answer pages (double-check position of figures)
\open0=v2ans2.inx
\chpar19←1 % this will prepare a ".JST" file containing justification statistics
\runninglefthead{ANSWERS TO EXERCISES}
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{ANSWER PAGES for THE ART OF COMPUTER PROGRAMMING}
\ctrline{(Volume 2)}
\ctrline{(second half of the answers)}
\ctrline{$\copyright$ 1980 Addison--Wesley Publishing Company, Inc.}
\vfill
\ninepoint
\runningrighthead{ANSWERS TO EXERCISES}
\section{4.1}
\eject
\setcount0 562
% Page 562
% folio 723 galley 10b 	*
\def\sim{\mathrel{\char'430}}
\ansbegin{4.1}

\ansno 1. 1010, 1011, 1000, $\ldotss$,
11000, 11001, 11110.

\ansno 2. (a)\9 $-110001$, $-11.001001001001 \ldotss
$, $11.0010010000111111 \ldotss\,$.

(b)\9 $11010011$, $1101.001011001011 \ldotss$ , $111.011001000100000
\ldotss\,$.

\def\≡{\overline1}
(c)\9 $\≡11\≡\≡$, $\≡0.0\≡\≡0110\≡\≡011 \ldotss
$, $10.011\≡111\≡ \ldotss\,$.

(d)\9 $-9.4$, $- \ldotsm 7582417582413$, $\ldotss 562951413$.

\ansno 3. $(1010113.2)↓{2i}$.

\ansno 4. (a)\9 Between rA and rX.\xskip (b) The remainder
in rX has radix point between bytes 3 and 4; the quotient in
rA has radix point one byte to the right of the least significant
portion of the register.

\ansno 5. It has been subtracted from $999 \ldotsm
9 = 10↑{\mskip 1mu p} - 1$, instead of from $1000 \ldotsm 0 = 10↑{\mskip 1mu p}$.

\ansno 6. (a,c)\9 $2↑{\mskip 1mu p-1} - 1$, $-(2↑{\mskip 1mu p-1} - 1)$;\xskip (b) $2↑{\mskip 1mu p-1}
- 1$, $-2↑{\mskip 1mu p-1}$.

\ansno 7. A ten's complement representation for
a negative number $x$ can be obtained by considering $10↑n +
x$ (where $n$ is large enough for this to be positive) and extending
it on the left with infinitely many nines. The nines' complement
representation can be obtained in the usual manner.\xskip (These two
representations are equal for nonterminating decimals, otherwise
the nines' complement representation has the form $\ldotss (a)99999
\ldots$ while the ten's complement representation has the form
$\ldotss (a + 1)0000 \ldotss\,$.) The representations may be
considered sensible if we regard the value of the infinite sum
$N = 9 + 90 + 900 + 9000 + \cdots$ as $-1$, since $N
- 10N = 9$.

See also exercise↔31, which considers $p$-adic
number systems. The latter agree with the $p$'s complement notations
considered here, for numbers whose radix-$p$ representation
is terminating, but there is no simple relation between the
field of $p$-adic numbers and the field of real numbers.

\ansno 8. $\sum ↓j a↓jb↑j = \sum ↓j (a↓{kj+k-1}b↑{k-1}
+ \cdots + a↓{kj})b↑{kj}$.

\ansno 9. {\tt A BAD AD0BE FACADE FADED}.\xskip [{\sl Note:}
Other possible ``\α{number sentences}'' would be \.{D0} \.{A} \.{DEED} \.{A}
\.{DECADE}; \.{A} \.{CAD} \.{FED} \.{A} \.{BABE} \.{BEEF},
\.{C0C0A}, \.{C0FFEE}; \.{B0B} \.{FACED} \.{A} \.{DEAD} \.{D0D0}.]
% Vicinity of page 562
% folio 725 galley 1 	*
\ansno 10. $\dispstyle
\left[\vcenter{\halign{\rt{$#$}⊗\rt{$\,#$}⊗\rt{$\,#$}⊗\rt{$\,
#$}⊗\rt{$\,#$}⊗\rt{$\;#$}⊗\rt{$\;#\ldotsm$}\cr
\ldotsm,⊗a↓3,⊗a↓2,⊗a↓1,⊗a↓0;⊗a↓{-1},⊗a↓{-2},\cr
\ldotsm,⊗b↓3,⊗b↓2,⊗b↓1,⊗b↓0;⊗b↓{-1},⊗b↓{-2},\cr}}\right]=
\left[\vcenter{\halign{\rt{$#$}⊗\rt{$\,#$}⊗\rt{$\,#$}⊗\rt{$\,
#$}⊗\rt{$\,#$}⊗\rt{$\;#$}⊗\rt{$\;#\ldotsm$}\cr
\ldotsm,⊗A↓3,⊗A↓2,⊗A↓1,⊗A↓0;⊗A↓{-1},⊗A↓{-2},\cr
\ldotsm,⊗B↓3,⊗B↓2,⊗B↓1,⊗B↓0;⊗B↓{-1},⊗B↓{-2},\cr}}\right]$, if
$$A↓j=\left[\vcenter{\halign{\rt{$# $}⊗\rt{$\,#,\ldotss,$}⊗\rt{$\,#$}\cr
a↓{k↓{j+1}-1},⊗a↓{k↓{j+1}-2}⊗a↓{k↓j}\cr
⊗b↓{k↓{j+1}-2}⊗b↓{k↓j}\cr}}\right],\qquad B↓j=b↓{k↓{j+1}-1}\ldotsm b↓{k↓j},$$
where $\langle k↓n\rangle$ is any infinite sequence
of integers with $k↓{j+1} > k↓j$.

\ansno 11. (The following algorithm works both for addition
or subtraction, depending on whether the plus or minus sign
is chosen.)

Start by setting $k ← a↓{n+1} ← a↓{n+2} ← b↓{n+1}
← b↓{n+2} ← 0$; then for $m = 0$, 1, $\ldotss$, $n + 2$ do the following:
Set $c↓m ← a↓m \pm b↓m + k$; then if $c↓m ≥ 2$, set $k ← -1$
and $c↓m ← c↓m - 2$; otherwise if $c↓m < 0$, set $k ← 1$ and $c↓m ← c↓m
+ 2$; otherwise (i.e., if $0 ≤ c↓m ≤ 1$), set $k ← 0$.

\ansno 12. (a)\9 Subtract $\pm(\ldotsm a↓30a↓10)↓{-2}$ from $\pm
(\ldotsm a↓40a↓20a↓0)↓{-2}$
in the negabinary system.\xskip (See also exercise 7.1--18 for a trickier
solution that uses full-word logical operations.)\xskip
(b) Subtract $(\ldotsm b↓30b↓10)↓2$
from $(\ldotsm b↓40b↓20b↓0)↓2$ in the binary system.

\ansno 13. $(1.909090\ldotsm)↓{-10} = (0.090909\ldotsm)↓{-10} = {1\over 11}$.

\ansno 14. \save7\hbox to 329pt{$\def\\{\hskip 4.5pt}\hskip0pt plus 200pt
\teqalign{\vbox to 10pt{}1\\1\\3\\2\\1⊗\qquad[5-4i]\cr
1\\1\\3\\2\\1⊗\qquad[5-4i]\cr
\noalign{\vskip -7.6pt}
\vbox{\hrule width 40.5pt}\cr
\noalign{\vskip-1.75pt}
1\\1\\3\\2\\1\cr
1\\1\\2\\0\\2\\\\\cr
1\\2\\1\\2\\3\\\\\\\\\cr
1\\1\\3\\2\\1\\\\\\\\\\\\\cr
1\\1\\3\\2\\1\\\\\\\\\\\\\\\\\cr
\noalign{\vskip 3pt\hrule width 76.5pt\vskip 3pt}
\lower5pt\null0\\1\\0\\3\\1\\1\\2\\0\\1⊗\qquad[9-40i]\cr}\hskip0pt plus 200pt$}\!
\raise 10pt\hbox{\lower 1ht7\box7}

\ansno 15. $[-{10\over 11}, {1\over 11}]$, and the rectangle
shown in Fig.\ A--6.

\topinsert{\vskip 40mm 
\inx{COPY PREP: Fig A-6 to be inserted}
\moveright 190pt\hbox par 128pt{\caption Fig.\ A--6.
Fundamental region for quater-imaginary numbers.}}

\ansno 16. It is tempting to try to do this in a very simple
way, by using the rule $2 = (1100)↓{i-1}$ to take care of carries;
but that leads to a nonterminating method if, for example, we try to add 1
to $(11101)↓{i-1} = -1$.

The following solution does the job by providing
four related algorithms (namely for adding or subtracting 1
or $i$). If $α$ is a string of zeros and ones, let $α↑{\mskip 1mu p}$ be
a string of zeros and ones such that $(α↑{\mskip 1mu p})↓{i-1} = (α)↓{i-1}
+ 1$; and let $α↑{-P}$, $α↑Q$, $α↑{-Q}$ be defined similarly, with
$-1$, $+i$, and $-i$ respectively in place of $+1$. Then
$$\eqalign{(α0)↑{\mskip 1mu p}⊗=α1;\cr(αx0)↑{-P}⊗=α↑{-Q}x1;\cr}\quad
\eqalign{(αx1)↑{\mskip 1mu p}⊗=α↑Qx0.\cr(α1)↑{-P}⊗=α0.\cr}\qquad\qquad
\eqalign{(α0)↑Q⊗=α↑{\mskip 1mu p}1;\cr(α0)↑{-Q}⊗=α↑Q1;\cr}\quad
\eqalign{(α1)↑Q⊗=α↑{-Q}0.\cr(α1)↑{-Q}⊗=α↑{-P}0.\cr}$$
Here $x$ stands for either 0 or 1, and the strings are
extended on the left with zeros if necessary. The processes
will clearly always terminate. Hence every number of the form
$a + bi$ with $a$ and $b$ integers is representable in the $i - 1$
system.

\ansno 17. No (in spite of exercise↔28); the number $-1$ cannot be so represented.
This can be proved by constructing a set $S$ as in Fig.↔1. We do have
the representations $-i = (0.1111\ldotsm)↓{1+i}$, $i = (100.1111\ldotsm
)↓{1+i}$.

\lineskip 0pt
\ansno 18. Let $S↓0$ be the set of points $(a↓7a↓6a↓5a↓4a↓3a↓2a↓1a↓0)↓{i-1}$,
where each $a↓k$ is 0 or 1.\xskip (Thus, $S↓0$ is given by the 256 interior
dots shown in Fig.↔1, if that picture is multiplied by↔16.)\xskip
We first show that $S$ is closed: If $y↓1$, $y↓2$, $\ldots$ is an
infinite subset of $S$, we have $y↓n = \lower7pt\null
\sum ↓{k≥1\lower 1pt\null} a↓{nk}16↑{-k}$,
where each $a↓{nk}$ is in $S↓0$. Construct a tree whose nodes
are $(a↓{n1}, \ldotss , a↓{nr})$, for $1 ≤ r ≤ n$, and let a
node of this tree be an ancestor of another node if it is an
initial subsequence of that node. By the infinity lemma this
tree has an infinite path $(a↓1, a↓2, a↓3, \ldotss)$, and it follows that $\sum
↓{k≥1} a↓k16↑{-k}$ is a limit point of $\{y↓1, y↓2, \ldotss\}$
in $S$.

\lineskip 1pt
By the answer to exercise↔16, all numbers of the
form $(a + bi)/16↑k$ are representable, when $a$ and $b$ are
integers. Therefore if $x$ and $y$ are arbitrary reals and $k
≥ 1$, the number $z↓k = (\lfloor 16↑kx\rfloor + \lfloor 16↑ky\rfloor
i)/16↑k$ is in $S + m + ni$ for some integers $m$ and $n$. It
can be shown that $S + m + ni$ is bounded away from the origin
when $(m, n) ≠ (0, 0)$. Consequently if $|x|$ and $|y|$ are
fixed and $k$ is sufficiently large, we have $z↓k
\in S$, and $\lim↓{k→∞}z↓k = x + yi$ is in $S$.

	[B. \α{Mandelbrot} calls $S$ the ``\α{twindragon},'' since he noticed
that it is essentially obtained by joining two ``\α{dragon curve}s'' belly-to-belly;
see his book {\sl Fractals: Form, Chance, and Dimension} (San Francisco: Freeman,
1977), 313--314. Other properties of the dragon curve are described in
C. \α{Davis} and D. E. \α{Knuth,} {\sl J. Recr.\ Math.\ \bf3} (1970),
66--81, 133--149.]

\ansno 19. If $m > u$ or $m < l$, find $a \in D$ such that $m
≡ a \modulo b$; the desired representation will be a representation
of $m↑\prime = (m - a)/b$ followed by $a$. Note that $m > u$
implies $l < m↑\prime < m$; $m < l$ implies $m < m↑\prime < u$;
so the algorithm terminates.

[There are no solutions when $b = 2$. The representation
will be unique iff $0 \in D$; nonunique representation occurs
for example when $D = \{-3, -1, 7\}$, $b = 3$, since $(α)↓3 =
(\overline377\overline3α)↓3$. When $b ≥ 3$ it is not difficult
to show that there are exactly $2↑{b-3}$ solution sets $D$ in
which $|a| < b$ for all $a \in D$. Furthermore the set $D =
\{0$, 1, $2 - ε↓2b↑n$, $3 - ε↓3b↑n$, $\ldotss$, $b - 2 - ε↓{b-2}b↑n$, $b
- 1 - b↑n\}$ gives unique representations, for all $b ≥ 3$ and
$n ≥ 1$, when each $ε↓j$ is 0 or 1. Reference: {\sl Proc.\ IEEE Symp.\ Comp.\
Arith.\ \bf4} (1978), 1--9.]

\ansno 20. (a)\9 $0.\overline1\overline1\overline1\,\ldots=\overline1.888\,
\ldots=\overline18.{111\atop777}\,\ldots=\overline18{1\atop7}.{222\atop666}\,
\ldots=\cdots=\overline18{123456\atop765432}.{777\atop111}\,\ldots$ has
nine representations.\xskip (b) A ``$D$-fraction'' $.a↓1a↓2\,\ldots$
always lies between $-1/9$ and $+71/9$. Suppose $x$ has ten or more
$D$-decimal representations. Then for sufficiently large $k$,
$10↑kx$ has ten representations that differ to the left of the
decimal point: $10↑kx = n↓1 + f↓1 = \cdots = n↓{10} + f↓{10}$
where each $f↓j$ is a $D$-fraction. By uniqueness of integer representations,
the $n↓j$ are distinct, say $n↓1 < \cdots < n↓{10}$, hence $n↓{10}
- n↓1 ≥ 9$; but this implies $f↓1 - f↓{10} ≥ 9 > 71/9 - (-1/9)$,
a contradiction.\xskip (c) Any number of the form $0.a↓1a↓2 \ldotsm
$, where each $a↓j$ is $-1$ or 8, equals $\overline1.a↓1↑\prime a↓2↑\prime
\,\ldots$ where $a↑\prime↓{j} = a↓j + 9$ (and it even has six
{\sl more} representations $\overline18.a↑{\prime\prime}↓1a↑{\prime\prime}↓2
\ldotsm$, etc.).

\ansno 21. We can convert to such a representation by using
a method like that suggested in the test for converting to balanced
ternary.

In contrast to the systems of exercise↔20, zero
can be represented in infinitely many ways, all obtained from
${1\over 2} + \sum ↓{k≥1}(-4{1\over 2}) \cdot 10↑{-k}$ (or
from the negative of this representation) by multiplying it
by a power of ten. The representations of unity are $1{1\over
2} - {1\over 2}$, ${1\over 2} + {1\over 2}$, $5 - 3{1\over
2} - {1\over 2}$, $5 - 4{1\over 2} + {1\over 2}$, $50 - 45
- 3{1\over 2} - {1\over 2}$, $50 - 45 - 4{1\over 2} + {1\over
2}$, etc., where $\pm {1\over 2} = (\pm 4{1\over 2})(10↑{-1}
+ 10↑{-2} + \cdotss)$.\xskip [{\sl AMM \bf 57} (1950), 90--93.]

\ansno 22. Given some approximation $b↓n \ldotsm
b↓1b↓0$ with error $\sum ↓{0≤k≤n}b↓k10↑k
- x > 10↑{-t}$ for $t > 0$, we will show how to reduce the error
by approximately $10↑{-t}$.\xskip (The process can be started by finding
a suitable $\sum ↓{0≤k≤n} b↓k10↑k > x$; then a finite
number of reductions of this type will make the error less than
$ε$.)\xskip Simply choose $m > n$ so large that the decimal representation
of $-10↑mα$ has a one in position $10↑{-t}$ and no ones in positions
$10↑{-t+1}$, $10↑{-t+2}$, $\ldotss$, $10↑n$. Then $10↑mα + ($a suitable
sum of powers of 10 between $10↑m$ and $10↑n) + \sum ↓{0≤k≤n}
b↓k10↑k \approx \sum ↓{0≤k≤n}b↓k10↑k - 10↑{-t}$.

\ansno 23. The set $S = \leftset\sum ↓{k≥1} a↓kb↑{-k}\relv a↓k \in
D\rightset$ is closed as in exercise↔18, hence it is
measurable, and in fact
it has positive measure. Since $bS = \union↓{a\in D}(a + S)$, we
have $b\mu (S) = \mu (bS) ≤ \sum ↓{a\in D}\mu (a + S) = \sum
↓{a\in D}\mu (S) = b\mu (S)$, and we must therefore have $\mu \biglp
(a + S) ∩ (a↑\prime + S)\bigrp = 0$ when $a ≠ a↑\prime \in D$.
Now $T$ has measure zero
since it is a union of countably many sets of the form $10↑k\biglp
n + ((a + S) ∩ (a↑\prime + S))\bigrp$, $a ≠ a↑\prime $, each
of measure zero.

[The set $T$ cannot be empty, since the real numbers
cannot be written as a countable union of disjoint, closed,
bounded sets; cf.\ {\sl AMM \bf 84} (1977), 827--828.
If $D$ has less than $b$ elements, the set of
numbers representable with radix $b$ and digits from $D$ has
measure zero. If $D$ has more than $b$ elements and represents all
reals, $T$ has infinite measure.]

\ansno 24. $\leftset 2a\cdot10↑k+a↑\prime\relv0≤a<5,0≤a↑\prime<2\rightset$
or $\leftset 5a↑\prime\cdot10↑k+a\relv0≤a<5,0≤a↑\prime<2\rightset$,\linebreak
for $k ≥ 0$.\xskip [R. L. \α{Graham} has shown
that there are no more sets of integer digits with these properties.
And Andrew \α{Odlyzko} has shown that the restriction to integers
is superflous, in the sense that if the smallest two elements
of $D$ are 0 and 1, all the digits must be integers.\xskip {\sl Proof:}
Let $S=\leftset\sum↓{k<0}a↓kb↑k\relv a↓k\in D\rightset$ be the set of ``fractions,''
and let $X = \leftset(a↓n \ldotsm a↓0)↓b \relv a↓k \in D\rightset$
be the set of ``whole numbers''; then $[0, ∞) =
\lower6pt\null\union↓{x\in X}(x + S)$, and $(x + S) ∩ (x↑\prime + S)$ has measure
zero for $x ≠ x↑\prime \in X$. We have $(0, 1) \subset S$, and
by induction on $m$ we will prove that $(m, m + 1) \subset x↓m
+ S$ for some $x↓m \in X$. Let $x↓m\in X$ be such that $(m, m
+ ε)∩ (x↓m + S)$ has positive measure for all $ε > 0$. Then $x↓m
≤ m$, and $x↓m$ must be an integer lest $x↓{\lfloor x↓m\rfloor}
+ S$ overlap $x↓m + S$ too much. If $x↓m > 0$, the fact that
$(m - x↓m, m - x↓m + 1) ∩ S$ has positive measure implies by
induction that this measure is 1, and $(m, m + 1) \subset x↓m
+ S$ since $S$ is closed. If $x↓m = 0$ and $(m, m + 1) \not
\subset S$, we must have $m < x↑\prime↓{m}
< m + 1$ for some $x↑\prime↓{m} \in X$, where $(m, x↑\prime↓{m})
\subset S$; but then $1 + S$ overlaps $x↑\prime↓{m} + S$. See
{\sl Proc.\ London Math.\ Soc.}\ (3) {\bf18} (1978), 581--595.]

{\sl Note:} If we drop the restriction $0 \in D$, there {\sl
are} many other cases, some of which are quite interesting,
especially $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$, $\{1,
2, 3, 4, 5, 51, 52, 53, 54, 55\}$, and $\{2, 3, 4, 5, 6, 52, 53,
54, 55, 56\}$. Alternatively if we allow negative digits we obtain
many other solutions by the method of exercise↔19, plus further
sets of unusual digits like $\{-1, 0, 1, 2, 3, 4, 5, 6, 7, 18\}$ that don't meet
the conditions stated there. It appears hopeless to find
a nice characterization of all solutions with negative digits.]

\ansno 25. A positive number whose base $b$ representation has
$m$ consecutive $(b - 1)$'s to the right of the decimal point
must have the form $c/b↑n + (b↑m - \theta )/b↑{n+m}$, where
$c$ and↔$n$ are nonnegative integers and $0 < \theta ≤1$. So if $u/v$
has this form, we find that $b↑{m+n}u = b↑mcv + b↑mv - \theta
v$. Therefore $\theta v$ is an integer that is a multiple of
$b↑m$. But $0 < \theta v ≤ v < b↑m$.\xskip [There can be arbitrarily
long runs of other digits $aaaaa$, if $0 ≤ a < b - 1$,
for example in the representation of $a/(b - 1)$.]
% Vicinity of page 565
% folio 731 galley 2a 	*
\ansno 26. The proof of ``sufficiency'' is a straightforward
generalization of the usual proof for base $b$, by successively
constructing the desired representation. The proof of ``necessity''
breaks into two parts: If $β↓{n+1}$ is greater than $\sum ↓{k≤n}
c↓kβ↓k$ for some $n$, then $β↓{n+1} - ε$ has no representation
for small $ε$. If $β↓{n+1} ≤ \sum ↓{k≤n} c↓kβ↓k$ for all
$n$, but equality does not always hold, we can show that there are
two representations for certain $x$.\xskip [See {\sl Transactions
of the Royal Society of Canada}, series III, {\bf 46} (1952),
45--55.]

\ansno 27. Proof by induction on $|n|$: If $n$ is even we must
take $e↓0 > 0$, and the result follows by induction, since
$n/2$ has a unique such representation. If $n$ is odd, we must
take $e↓0 = 0$, and the problem reduces to representing $-(n
- 1)/2$; if the latter quantity is either zero or one, there
is obviously only one way to proceed, otherwise it has a unique reversing
representation by induction.

[It follows that every positive integer has exactly {\sl two} such
representations with {\sl decreasing} exponents $e↓0>e↓1>\cdots>e↓t$:
one with $t$ even and the other with $t$ odd.]

\ansno 28. A proof like that of exercise↔27 may be given. Note
that $a + bi$ is a multiple of $1 + i$ by a complex integer
if and only if $a + b$ is even. This representation is intimately
related to the \α{dragon curve} discussed in the answer to exercise 18.

\ansno 29. It suffices to prove that any collection $\{T↓0, T↓1,
T↓2, \ldotss\}$ satisfying Property B may be obtained by collapsing
some collection $\{S↓0, S↓1, S↓2, \ldotss\}$, where $S↓0 = \{0, 1,
\ldotss , b - 1\}$ and all elements of $S↓1$, $S↓2$, $\ldots$ are
multiples of $b$.

To prove the latter statement, we may assume that
$1 \in T↓0$ and that there is a least element $b > 1$ such
that $b \notin T↓0$. We will prove, by induction on $n$,
that if $nb \notin T↓0$, then $nb + 1$, $nb + 2$, $\ldotss$,
$nb + b - 1$ are not in any of the $T↓j$'s; but if $nb \in
T↓0$, then so are $nb + 1$, $\ldotss$, $nb + b - 1$. The result then
follows with $S↓1 = \leftset nb \relv nb \in T↓0\rightset$, $S↓2 = T↓1$, $S↓3 =
T↓2$, etc.

If $nb \notin T↓0$, then $nb = t↓0 + t↓1+
\cdotss$, where $t↓1$, $t↓2$, $\ldots$ are multiples of $b$; hence
$t↓0 < nb$ is a multiple of $b$. By induction, $(t↓0 + k) +
t↓1 + t↓2 + \cdots$ is the representation of $nb
+ k$, for $0 < k < b$; hence $nb + k \notin T↓j$ for any
$j$.

If $nb \in T↓0$ and $0 < k < b$, let the representation
of $nb + k$ be $t↓0 + t↓1 + \cdotss$. We cannot have $t↓j =
nb + k$ for $j ≥ 1$, lest $nb + b$ have two representations
$(b - k) + \cdots + (nb + k) + \cdots = (nb) + \cdots + b +
\cdotss$. By induction, $t↓0 \mod b = k$; and the representation
$nb = (t↓0 - k) + t↓1 + \cdots$ implies that $t↓0
= nb + k$.

[Reference: {\sl Nieuw Archief voor Wiskunde} (3)
{\bf 4} (1956), 15--17. A finite analog of this result was derived
by P. A. \α{MacMahon,} {\sl Combinatory Analysis \bf 1} (1915),
217--223.]

\ansno 30. (a)\9 Let $A↓j$ be the set of numbers $n$ whose representation
does not involve $b↓j$; then by the uniqueness property, $n
\in A↓j$ iff $n + b↓j \notin A↓j$. Consequently we have $n \in
A↓j$ iff $n + 2b↓j \in A↓j$. It follows that, for $j ≠ k$, $n \in
A↓j ∩ A↓k$ iff $n + 2b↓jb↓k \in A↓j ∩ A↓k$. Let $m$ be the number
of integers $n \in A↓j ∩ A↓k$ such that $0 ≤ n < 2b↓jb↓k$. Then
this interval contains exactly $m$ integers that are in
$A↓j$ but not $A↓k$, exactly $m$ in $A↓k$ but not $A↓j$, and
exactly $m$ in neither $A↓j$ nor $A↓k$; hence $4m = 2b↓jb↓k$.
Therefore $b↓j$ and $b↓k$ cannot both be odd. But at least one
$b↓j$ is odd, of course, since odd numbers can be represented.\xskip
(b) According to (a) we can renumber the $b$'s so that $b↓0$ is odd and
$b↓1$, $b↓2$, $\ldots$ are even; then ${1\over2}b↓1$, ${1\over2}b↓2$,
$\ldots$ must also be a binary basis, and the process can be iterated.

(c)\9 If it is a binary basis, we must have positive and negative $d↓k$'s for
arbitrarily large $k$, in order to represent $\pm2↑n$ when $n$ is large.
Conversely, the following algorithm may be used:

\algstep S1. [Initialize.] Set $k←0$.

\algstep S2. [Done?] If $n=0$, terminate.

\algstep S3. [Choose.] If $n$ is odd, include $2↑kd↓k$ in the representation,
and set $n ← (n-d↓k)/2$. Otherwise set $n←n/2$.

\algstep S4. [Advance $k$.] Increase $k$ by 1 and return to S2.\quad\blackslug

\yskip At each step the choice is forced; furthermore
step S3 always decreases $|n|$ unless $n=-d↓k$, hence the algorithm must terminate.

(d)\9 Two iterations of steps S2--S4 in the preceding algorithm will change
$4m→m$, $4m+1→m+5$, $4m+2→m+7$, $4m+3→m-1$. Arguing as in exercise↔19, we
need only show that the algorithm terminates for $-2≤n≤8$; all other values of
$n$ are moved toward this interval. In this
range $3 → -1 → -2 → 6 → 8 → 2 → 7 → 0$ and $4 → 1 → 5 → 6$.
Thus $1 = 7 \cdot 2↑0 - 13 \cdot 2↑1 + 7 \cdot 2↑2 - 13 \cdot
2↑3 - 13 \cdot 2↑5 - 13 \cdot 2↑9 + 7 \cdot 2↑{10}$.

{\sl Note:} The choice $d↓0$, $d↓1$, $d↓2$, $\ldots
= 5$, $-3$, 3, 5, $-3$, 3, $\ldots$ also yields a binary basis. For
further details see {\sl Math.\ Comp.\ \bf 18} (1964), 537--546;
A. D. \α{Sands,} {\sl Acta Mathematica}, Acad.\ Sci.\ Hung., {\bf 8}
(1957), 65--86.

\ansno 31. (See also the related exercises 3.2.2--11, 4.3.2--13,
4.6.2--22.)

(a)\9 By multiplying numerator and denominator by suitable powers
of↔2, we may assume that $u = (\ldotsm u↓2u↓1u↓0)↓2$ and $v =
(\ldotsm v↓2v↓1v↓0)↓2$ are 2-adic integers,
where ${v↓0 = 1}$. The following computational
method now determines $w$, using the notation $u↑{(n)}$ to stand
for the integer $(u↓{n-1} \ldotsm u↓0)↓2 = u \mod 2↑n$ when
$n > 0\,$:

Let $w↓0 = u↓0$ and $w↑{(1)}=w↓0$. For $n = 1$, 2, $\ldotss$, assume
that we have found an integer $w↑{(n)} = (w↓{n-1} \ldotsm w↓0)↓2$
such that $u↑{(n)} ≡ v↑{(n)}w↑{(n)} \modulo{2↑n}$.
Then we have $u↑{(n+1)} ≡ v↑{(n+1)}w↑{(n)}
\modulo {2↑n}$, hence $w↓n = 0$ or 1 according as the quantity
$(u↑{(n+1)} - v↑{(n+1)}w↑{(n)})\mod 2↑{n+1}$ is 0 or $2↑n$.

(b)\9 Find the smallest integer $k$ such that $2↑k
≡ 1 \modulo {2n + 1}$. Then we have $1/(2n + 1) = m/(2↑k - 1)$ for
some integer $m$, $1 ≤ m < 2↑{k-1}$. Let $α$ be the $k$-bit binary
representation of $m$; then $(0.ααα\ldotsm)↓2$ times $2n + 1$
is $(0.111\ldotsm)↓2 = 1$ in the binary system, and $(\ldotsm ααα)↓2$
times $2n + 1$ is $(\ldotsm 111)↓2 = -1$ in the 2-adic system.

(c)\9 If $u$ is rational, say $u = m/(2↑en)$ where
$n$ is odd and positive, the 2-adic representation of $u$ is
periodic, because the set of numbers with periodic expansions
includes $-1/n$ and is closed under the operations of negation,
division by 2, and addition. Con\-versely, if $u↓{N+λ}=u↓N$ for all
$N≥\mu$, the 2-adic number $(2↑λ-1)2↑{-\mu}\,u$ is an integer.

(d)\9 The square of any number of the form $(\ldotsm
u↓2u↓11)↓2$ has the form $(\ldotsm 001)↓2$, hence the condition
is necessary. To show the sufficiency, we can use the following procedure
to compute $v = \sqrt{n}$ when $n \mod 8 = 1$:

\algstep H1. [Initialize.] Set $m ← (n - 1)/8$, $k ← 2$, $v↓0 ←
1$, $v↓1 ← 0$, $v ← 1$.\xskip (During this algorithm we will have $v=(v↓{k-1}\ldotsm
v↓1v↓0)↓2$ and $v↑2=n-2↑{k+1}m$.)

\algstep H2. [Transform.] If $m$ is even, set $v↓k ← 0$,
$m ← m/2$. Otherwise set $v↓k ← 1$, $m ← (m - v - 2↑{k-1})/2$, $v
← v + 2↑k$.

\algstep H3. [Advance $k$.] Increase $k$ by 1 and return to H2.\quad\blackslug

\ansno 32. A generalization appears
in {\sl Math.\ Comp.\ \bf 29} (1975), 84--86.

\ansno 33. Let $K↓n$ be the set of all such $n$-digit numbers, so that
$k↓n=\|K↓n\|$. If $S$ and $T$ are any finite sets of integers, we shall say
$S\sim T$ if $S=T+x$ for some integer $x$, and we shall write $k↓n(S)=\|\Kscr↓n(S)\|$,
where $\Kscr↓n(S)$ is the family of all subsets of $K↓n$ that are $\sim S$. When
$n=0$, we have $k↓n(S)=0$ unless $\|S\|≤1$, since zero is the only ``0-digit''
number. When $n≥1$ and $S=\{s↓1,\ldotss,s↓r\}$, we have $$\twoline{\Kscr↓n(S)=
\union↓{0≤j<b}\,\,\union↓{(a↓1,\ldotss,a↓r)}\left.
\mathopen{\vcenter{\hbox{\:@\char'10}}}\,
\{t↓1b+a↓1,\ldotss,t↓rb+a↓r\}\;\right|}{4pt}{\{t↓1,\ldotss,t↓r\}\in K↓{n-1}\biglp
\leftset(S↓i+j-a↓i)/b\relv1≤i≤r\rightset\bigrp\,\mathclose{\vcenter{
\hbox{\:@\char'11}}},}$$
where the inner union is over all sequences of digits $(a↓1,\ldotss,a↓r)$ satisfying
the condition
$a↓i≡S↓i+j\modulo b$ for $1≤i≤r$. In this formula we require $t↓i-t↓{i↑\prime}
={(s↓i-a↓i)/b-(s↓{i↑\prime}-a↓{i↑\prime})/b}$ for $1≤i<i↑\prime≤r$, so that
the naming of subscripts is uniquely determined. By the principle of
\α{inclusion and exclusion}, therefore, we have $k↓n(S)=\sum↓{0≤j<b}\sum↓{m≥1}
(-1)↑{m-1}f(S,m,j)$, where $f(S,m,j)$ is the number of sets of integers that can
be expressed as $\{t↓1b+a↓1,\ldotss,t↓rb+a↓r\}$ in the above manner for $m$
different sequences $(a↓1,\ldotss,a↓r)$, summed over all choices of $m$ different
sequences $(a↓1,\ldotss,a↓r)$. Given $m$ different sequences $(a↓1↑{(l)},\ldotss,
a↓r↑{(l)})$ for $1≤l≤m$, the number of such sets is $k↓{n-1}\biglp\{(s↓i+j
-a↓i↑{(l)})/b\relv 1≤i≤r,1≤l≤m\}\bigrp$. Thus there is a collection of sets
$\Tscr(S)$ such that $$k↓n(S)=\sum↓{T\in\Tscr(S)}c↓T\,k↓{n-1}(T),$$
where each $c↓T$ is an integer. Furthermore if $T\in \Tscr(S)$, its elements
are near those of $S$; we have
$\min T≥(\min S-\max D)/b$ and $\max T≤(\max S+b-1-\min D)/b$. Thus we obtain
simultaneous recurrence relations for the sequences $\langle k↓n(S)\rangle$,
where $S$ runs through the nonempty integer subsets of $[l,u+1]$, in the notation of
exercise↔19. Since $k↓n=k↓n(S)$ for any one-element set $S$, the sequence
$\langle k↓n\rangle$ appears these recur\-rences. The coefficients $c↓T$ can
be computed from the first few values of $k↓n(S)$, so we can obtain a system of
equations defining the generating functions $k↓S(z)=\sum k↓n(S)z↑n=
{\biglp\|S\|≤1\bigrp}+z\sum↓{T\in\Tscr(S)}k↓T(z)$.

For example, when $D=\{-1,0,3\}$ and $b=3$ we have $l=-{3\over2}$ and $u={1\over2}$,
so the relevant sets $S$ are $\{0\}$, $\{0,1\}$, $\{-1,1\}$, and
$\{-1,0,1\}$. The corresponding sequences for $n≤3$ are $\langle1,3,8,21\rangle$,
$\langle0,1,3,8\rangle$, $\langle0,0,1,4\rangle$, and $\langle0,0,0,0\rangle$;
so we obtain
$$\eqalign{k↓0(z)⊗=1+z\biglp3k↓0(z)-k↓{01}(z)\bigrp,\cr
k↓{01}(z)⊗=zk↓0(z),\cr}\qquad\qquad
\eqalign{k↓{02}(z)⊗=z\biglp k↓{01}(z)+k↓{02}(z)\bigrp,\cr
l↓{012}(z)⊗=0,\cr}$$
and $k(z)=1/(1-3z+z↑2)$.
\inx{Fibonacci number}
In this case $k↓n=F↓{2n+2}$ and $k↓n\biglp\{0,2\}\bigrp=F↓{2n-1}-1$.
% Vicinity of page 568
% folio 733 galley 2b 	*
\ansbegin{4.2.1}

\def\\{\spose{\raise 3.825pt\hbox{\sl\hskip.05em\char'31}}} % \\h will be h bar
\ansno 1. $N = (62, +.60\ 22\ 52\ 00)$;
$\\h = (37, +.10\ 54\ 50\ 00)$. Note that $10\\h$ would be $(38, +.01\
05\ 45\ 00)$.

\ansno 2. $b↑{E-q}(1 - b↑{-p})$, $b↑{-q-p}$;\xskip $b↑{E-q}(1 - b↑{-p})$,
$b↑{-q-1}$.

\ansno 3. When $e$ does not have its smallest value,
the most significant ``one'' bit (which appears in all such
normalized numbers) need not appear in the computer word.

\ansno 4. $(51, +.10209877)$; $(50, +.12346000)$; $(53, +.99999999)$.
The third answer would be $(54, +.10000000)$ if the first operand
had been $(45, -.50000000)$.

\ansno 5. If $x \sim  y$ and $m$ is an integer then $mb + x \sim  mb
+ y$. Furthermore $x\sim y$ implies $x/b\sim y/b$, by considering all
possible cases. Another crucial property is that $x$ and $y$ will
round to the same integer, whenever $x \sim  y$.

Now if $b↑{-p-2}F↓v ≠ f↓v$ we must have $(b↑{\mskip 1mu p+2}f↓v)\mod
b ≠ 0$; hence the transformation leaves $f↓v$ unchanged unless
$e↓u - e↓v ≥ 2$. Since $u$ was normalized, it is nonzero and
$|f↓u + f↓v| > b↑{-1} - b↑{-2} ≥ b↑{-2}$: the leading nonzero
digit of $f↓u + f↓v$ must be at most two places to the right
of the radix point, and the rounding operation will convert
$b↑{\mskip 1mu p+j}(f↓u + f↓v)$ to an integer, where $j ≤ 1$. The proof
will be complete if we can show that $b↑{\mskip 1mu p+j+1}(f↓u + f↓v)
\sim  b↑{\mskip 1mu p+j+1}(f↓u + b↑{-p-2}F↓v)$. By the previous paragraph,
we have $b↑{\mskip 1mu p+2}(f↓u + f↓v) \sim  b↑{\mskip 1mu p+2}f↓u + F↓v = b↑{\mskip 1mu p+2}(f↓u
+ b↑{-p-2}F↓v)$, which implies the desired result for all $j
≤ 1$.

Note that, when $b > 2$ is even, such an integer
$F↓v$ always exists; but when $b = 2$ we require $p + 3$ bits
(let $2F↓v$ be an integer). When $b$ is odd, an integer $F↓v$
always exists except in the case of division, when a remainder
of ${1\over 2}b$ is possible.

\ansno 6. (Consider the case $e↓u = e↓v$, $f↓u = -f↓v$ in
Program↔A\null.)\xskip Register↔A retains its previous sign, as in \.{ADD}.

\ansno 7. Say that a number is normalized iff it is zero or
its fraction part lies in the range ${1\over 6} < |f| < {1\over 2}$.
A $(p + 1)$-place accumulator suffices for addition and subtraction;
rounding (except during division) is equivalent to truncation.
A very pleasant system indeed! We might represent numbers with
excess-zero exponent, inserted between the first and subsequent
digits of the fraction, and complemented if the fraction is
negative, so that fixed-point order is preserved.

\ansno 8. (a)\9 $(06, +.12345679) \oplus (06, -.12345678)$,\xskip $(01,
+.10345678) \oplus (00, -.94000000)$;\xskip\penalty1000 (b) $(99, +.87654321) \oplus
\hbox{itself}$,\xskip $(99, +.99999999) \oplus (91, +.50000000)$.

\ansno 9. $a = c = (-50, +.10000000)$, $b = (-41, +.20000000)$,
$d = (-41, +.80000000)$, $y = (11, +.10000000)$.

\ansno 10. $(50, +.99999000) \oplus (55, +.99999000)$.
% Vicinity of page 569
% folio 735 galley 3a 	*
\ansno 11. $(50, +.10000001) \otimes (50, +.99999990)$.

\ansno 12. If $0 < |f↓u| < |f↓v|$, then $|f↓u| ≤ |f↓v| - b↑{-p}$;
hence $1/b < |f↓u/f↓v| ≤ 1 - b↑{-p}/|f↓v| < 1 - b↑{-p}$. If
$0 < |f↓v| ≤ |f↓u|$, we have $1/b < |f↓u/f↓v|/b ≤ \biglp(1 - b↑{-p})/(1/b)\bigrp/b
= 1 - b↑{-p}$.

\ansno 13. See J. Michael \α{Yohe,} {\sl IEEE Transactions} {\bf C--22}
(1973), 577--586; cf.\ also exercise 4.2.2--24.

\mixans 14. {⊗FIX⊗STJ⊗9F⊗Float-to-fix subroutine:\cr
⊗⊗STA⊗TEMP\cr
⊗⊗LD1⊗TEMP(EXP)⊗$\rI1 ← e$.\cr
⊗⊗SLA⊗1⊗$\rA ← \pm\,f\,f\,f\,f\,0$.\cr
⊗⊗JAZ⊗9F⊗Is input zero?\cr
⊗⊗DEC1⊗1\cr
⊗⊗CMPA⊗=0=(1:1)⊗If leading byte is zero,\cr
⊗⊗JE⊗*-4⊗\quad shift left again.\cr
\\
⊗⊗ENN1⊗-Q-4,1\cr
⊗⊗J1N⊗FIXOVFLO⊗Is magnitude too large?\cr
\\
⊗⊗ENTX⊗0\cr
⊗⊗SRAX⊗0,1\cr
\\
⊗⊗CMPX⊗=1//2=\cr
⊗⊗JL⊗9F\cr
⊗⊗JG⊗*+2\cr
⊗⊗JAO⊗9F\cr
\\
⊗⊗STA⊗*+1(0:0)⊗Round, if necessary.\cr
⊗⊗INCA⊗1⊗Add $\pm 1$ (overflow is impossible).\cr
⊗9H⊗JMP⊗*⊗Exit from subroutine.\quad\blackslug\cr}

\mixans 15. {⊗FP⊗STJ⊗EXITF⊗Fractional part subroutine:\cr
⊗⊗JOV⊗OFLO⊗Ensure overflow is off.\cr
⊗⊗STA⊗TEMP⊗$\.{TEMP} ← u$.\cr
⊗⊗ENTX⊗0\cr
⊗⊗SLA⊗1⊗$\rA ← f↓u$.\cr
\\
⊗⊗LD2⊗TEMP(EXP)⊗$\rI2 ← e↓u$.\cr
⊗⊗DEC2⊗Q\cr
⊗⊗J2NP⊗*+3\cr
⊗⊗SLA⊗0,2⊗Remove integer part of $u$.\cr
⊗⊗ENT2⊗0\cr
⊗⊗JANN⊗1F\cr
\\
⊗⊗ENN2⊗0,2⊗Fraction is negative: find\cr
⊗⊗SRAX⊗0,2⊗\quad its complement.\cr
⊗⊗ENT2⊗0\cr
⊗⊗JAZ⊗*+2\cr
⊗⊗INCA⊗1\cr
⊗⊗ADD⊗WM1⊗Add word size minus one.\cr
\\
⊗1H⊗INC2⊗Q⊗Prepare to normalize the answer.\cr
⊗⊗JMP⊗NORM⊗Normalize, round, and exit.\cr
⊗8H⊗EQU⊗1(1:1)\cr
⊗WM1⊗CON⊗8B-1,8B-1(1:4)⊗Word size minus one\quad\blackslug\cr}

\ansno 16. If $|c| ≥ |d|$, then set $r ← d \odiv c$,
$s ← c \oplus (r \otimes d)$; $x ← \biglp a \oplus (b \otimes r)\bigrp
\odiv s$, $y ← \biglp b \ominus (a \otimes r)\bigrp \odiv
s$. Otherwise set $r ← c \odiv d$, $s ← d \oplus (r \otimes
c)$; $x ← \biglp (a \otimes r) \oplus b\bigrp \odiv s$, $y ← \biglp
(b \otimes r) \ominus a\bigrp \odiv s$. Then $x + iy$ is the
desired approximation to $(a + bi)/(c + di)$.\xskip [{\sl CACM \bf 5} (1963),
435. Other algorithms for complex arithmetic and function evaluation
are given by P. \α{Wynn,} {\sl BIT \bf 2} (1962), 232--255; see
also Paul \α{Friedland,} {\sl CACM \bf 10} (1967), 665.]

\ansno 17. See Robert \α{Morris,} {\sl IEEE Transactions} {\bf C--20}
(1971), 1578--1579. Error analysis is more difficult with such
systems, so \α{interval arithmetic} is correspondingly more desirable.

\ansno 18. For positive numbers: shift fraction left until $f↓1
= 1$, then round, then if the fraction is zero (rounding overflow)
shift it right again. For negative numbers: shift fraction left
until $f↓1 = 0$, then round, then if the fraction is zero (rounding
underflow) shift it right again.

\ansno 19. $\biglp 43 + (1$ if $e↓v < e↓u) - (1$ if fraction overflow$)
- (10$ if result zero$) + (4$ if magnitude
is rounded up$) + (1$ if first rounding digit is $b/2) + (5$ if
rounding digits are $b/2\ 0 \ldotsm 0) + (7$↔if rounding overflow$)
+ 7N + A(-1 + (11$ if $N > 0))\bigrp u$, where $N$ is the number
of left shifts during normalization and $A = 1$ if rX receives
nonzero digits (otherwise $A = 0$). The maximum time of $73u$
occurs for example when $$u = +50\ 01\ 00\ 00\ 00,\quad v = -46\ 49\ 99\
99\ 99,\quad b = 100.$$ [The average time, considering the
data in Section 4.2.4, will be about $45{1\over 2}u$.]

% Vicinity of page 570
% folio 738 galley 3b 	*
\ansbegin{4.2.2}

\ansno 1. $u \ominus v = u \oplus -v
= -v \oplus u = -(v \oplus -u) = -(v \ominus u)$.

\ansno 2. $u \oplus x ≥ u \oplus 0 = u$, by (8), (2), (6); hence
by (8) again, $(u \oplus x) \oplus v ≥ u \oplus v$. Similarly,
(8) and (6) together with (2) imply that $(u \oplus x) \oplus
(v \oplus y) ≥ (u \oplus x) \oplus v$.

\ansno 3. $u = 8.0000001$, $v = 1.2500008$, $w = 8.0000008$;
$(u \otimes v) \otimes w = 80.000064$, $u \otimes (v \otimes w)=
80.000057$.

\ansno 4. Yes; let $1/u \approx v = w$, where $v$
is large.

\ansno 5. Not always; in decimal arithmetic take $u = v = 9$.

\ansno 6. (a)\9 Yes.\xskip (b) Only for $b + p ≤ 4$ (try
$u = 1 - b↑{-p}$).\xskip [W. M. \α{Kahan} observes that the identity {\sl
does\/} hold whenever $b↑{-1} ≤ f↓u ≤ b↑{-1/2}$. It follows that
$1 \odiv \biglp 1 \odiv (1 \odiv u)\bigrp = 1 \odiv
u$ for all $u$.]

\def\expcirc#1{{\hbox to 9pt{\hfill
\hbox to 0pt{\hskip 0pt minus 100pt\raise 5.0833pt
\hbox{\:@\char'142}\hskip 0pt minus 100pt}\!
\hbox to 0pt{\hskip 0pt minus 100pt\:e#1\hskip 0pt minus 100pt}\hfill}}}
\ansno 7. If $u$ and $v$ are consecutive floating binary numbers,
$u \oplus v = 2u$ or $2v$. When it is $2v$ we often have $u↑\expcirc2\oplus
v↑\expcirc2<2v↑\expcirc2$. For example,
$u = (.10 \ldotsm 001)↓2$, $v = (.10 \ldotsm 010)↓2$, $u \oplus v = 2v$,
and $u↑\expcirc2+v↑\expcirc2=(.10 \ldotsm 011)↓2$.

\ansno 8. (a)\9 $\sim $, $\approx$;\xskip (b) $\sim $, $\approx$;\xskip (c)
$\sim $, $\approx$;\xskip (d) $\sim $;\xskip (e) $\sim $.

\ansno 9. $|u - w| ≤ |u - v| + |v - w| ≤ ε↓1 \min(b↑{e↓u
-q}, b↑{e↓v-q}) + ε↓2 \min(b↑{e↓v-q}, b↑{e↓w
-q}) ≤ ε↓1b↑{e↓u-q}+ε↓2b↑{e↓w-q} ≤ (ε↓1
+ ε↓2)\max(b↑{e↓u-q}, b↑{e↓w-q})$. The result
cannot be strengthened in general, since for example we might
have $e↓u$ very small compared to both $e↓v$ and $e↓w$, and
this means that $u - w$ might be fairly large under the hypotheses.

\ansno 10. We have $(.a↓1 \ldotsm a↓{p-1}a↓p)↓b \otimes
(.9 \ldotsm 99)↓b = (.a↓1 \ldotsm a↓{p-1}(a↓p - 1))↓b$ if $a↓p
≥ 1$; here ``9'' stands for $b - 1$. Furthermore, $(.a↓1 \ldotsm
a↓{p-1}a↓p)↓b \otimes (1.0 \ldotsm 0)↓b = (.a↓1 \ldotsm a↓{p-1}0)↓b$, so
the multiplication is not monotone if $b>2$ and $a↓p≥2$. 
But when $b = 2$, this argument
can be extended to show that multiplication {\sl is} monotone; obviously
the ``certain computer'' had $b > 2$.

\ansno 11. Without loss of generality, let $x$ be an integer,
$|x| < b↑{\mskip 1mu p}$. If $e ≤ 0$, then $t = 0$. If $0 < e ≤ p$, then $x
- t$ has at most $p + 1$ digits, the least significant being
zero. If $e > p$, then $x - t = 0$.\xskip [The result holds also under
the weaker hypothesis $|t| < 2b↑e$.]

\def\dprime{↑{\prime\prime}}
\ansno 12. Assume that $e↓u = p$, $e↓v ≤ 0$, $u > 0$. Case 1, $u
> b↑{\mskip 1mu p-1}$. Case (1a), $w=u+1$, $v≥{1\over2}$, $e↓v=0$. Then
$u↑\prime=u$ or $u+1$, $v↑\prime=1$, $u\dprime=u$, $v\dprime=1$ or 0.
Case (1b), $w = u$, $|v| ≤ {1\over 2}$. Then $u↑\prime
= u$, $v↑\prime = 0$, $u\dprime = u$, $v\dprime = 0$. If $|v| = {1\over
2}$ and more general rounding is permitted we might also have
$u↑\prime = u \pm 1$, $v\dprime = \mp1$. Case (1c), $w = u - 1$, $v ≤ -{1\over 2}$,
$e↓v = 0$. Then $u↑\prime = u$ or $u - 1$, $v↑\prime = -1$, $u\dprime
= u$, $v\dprime = -1$ or 0. Case 2, $u = b↑{\mskip 1mu p-1}$. Case (2a),
$w = u + 1$, $v ≥ {1\over 2}$, $e↓v = 0$. Like (1a). Case (2b),
$w = u$, $|v| ≤ {1\over 2}$, $u↑\prime ≥ u$. Like (1b). Case (2c),
$w = u$, $|v| ≤ {1\over 2}$, $u↑\prime < u$. Then $u↑\prime = u
- j/b$ where $v = j/b + v↓1$ and $|v↓1| ≤ {1\over 2}b↑{-1}$ for
some positive integer $j ≤ {1\over 2}b$; we have $v↑\prime =
0$, $u\dprime = u$, $v\dprime = j/b$. Case (2d), $w < u$. Then $w
= u - j/b$ where $v = -j/b + v↓1$ and $|v↓1| ≤ {1\over 2}b↑{-1}$
for some positive integer $j ≤ b$; we have $(v↑\prime , u\dprime
) = (-j/b, u)$, and $(u↑\prime , v\dprime ) = (u, -j/b)$ or
$\biglp u - 1/b, (1 - j)/b\bigrp $, the latter case only when $v↓1
= {1\over 2}b↑{-1}$. In all cases $u \ominus u↑\prime = u -
u↑\prime$, $v \ominus v↑\prime = v - v↑\prime$, $u \ominus u\dprime
= u - u\dprime$, $v \ominus v\dprime = v - v\dprime $, round$(w
- u - v) = w - u - v$.

\ansno 13. Since round$(x) = 0$ iff $x = 0$, we want to find a large set of
integer pairs $(m, n)$ with the property that $m \odiv n$ is
an integer iff $m/n$ is. Assume that $|m|, |n| < b↑{\mskip 1mu p}$. If $m/n$
is an integer, then $m \odiv n = m/n$ is also. Conversely if
$m/n$ is not an integer, but $m\odiv n$ is, we have $1/|n|
≤ |m\odiv n - m/n| < {1\over 2} |m/n| b↑{1-p}$, hence $|m|
> 2b↑{\mskip 1mu p-1}$. Our answer is therefore to require $|m| ≤ 2b↑{\mskip 1mu p-1}$
and $0 < |n| < b↑{\mskip 1mu p}$.\xskip (Slightly weaker hypotheses are also possible.)

\ansno 14. $|(u \otimes v) \otimes w - uvw| ≤ |(u \otimes v)
\otimes w - (u \otimes v)w| + |w|\,|u \otimes v - uv| ≤ \delta
↓{(u\otimes v)\otimes w} + b↑{e↓w-q-l↓w}\delta ↓{u\otimes v}
≤ (1 + b) \delta ↓{(u\otimes v)\otimes w}$. Now $|e↓{(u\otimes v)\otimes w}
- e↓{u\otimes(v\otimes w)}| ≤ 2$, so we may take $ε = {1\over 2}(1
+ b)b↑{2-p}$.

\ansno 15. $u ≤ v$ implies that $(u \oplus u) \odiv 2 ≤ (u
\oplus v) \odiv 2 ≤ (v \oplus v) \odiv 2$, so the condition
holds for all $u$ and $v$ iff it holds whenever $u = v$. For
base $b = 2$, the condition is therefore always satisfied (barring
overflow); but for $b > 2$ there are numbers $v ≠ w$ such that
$v \oplus v = w \oplus w$, hence the condition fails.\xskip [On the
other hand, the formula $u \oplus \biglp (v \ominus u) \odiv
2\bigrp$ does give a midpoint in the correct range. {\sl Proof:
}It suffices to show that $u + (v \ominus u) \odiv 2 ≤
v$, i.e., $(v \ominus u) \odiv 2 ≤ v - u$; and it is easy
to verify that round$\biglp{1\over 2}\hbox{round}(x)\bigrp ≤ x$
for all $x ≥ 0$.]

\ansno 16. (a)\9 Exponent changes occur at $\sum ↓{10} = 11.111111$,
$\sum ↓{91} = 101.11111$, $\sum ↓{901} = 1001.1102$, $\sum ↓{9001}
= 10001.020$, $\sum ↓{90009} = 100000.91$, $\sum ↓{900819} = 1000000.0$;
therefore $\sum ↓{1000000} = 1109099.1$.

\vskip 2pt
(b)\9 $\sum ↓{1≤k≤n} 1.2345679
= 1224782.1$, and (14) tries to take the square root of $-.0053187053$.
But (15) and (16) are exact in this case.\xskip [If $x↓k = 1 + \lfloor
(k - 1)/2\rfloor 10↑{-7}$, (15) and (16) have errors of order
$n$. See \α{Chan} and \α{Lewis}, {\sl CACM \bf22} (1979), 526--531, for further results
on the accuracy of standard deviation calculations.]

(c)\9 We need to show that $u \oplus \biglp(v \ominus
u) \odiv k\bigrp$ lies between $u$ and $v$; see exercise↔15.

\mixans 17. {⊗FCMP⊗STJ⊗9F⊗Floating point comparison subroutine:\cr
⊗⊗JOV⊗OFLO⊗Ensure overflow is off.\cr
⊗⊗STA⊗TEMP\cr
⊗⊗LDAN⊗TEMP⊗$v ← -v$.\cr
\noalign{\vskip 3pt
\hbox{\quad (Copy here lines 07--20 of Program 4.2.1A.)}\vskip3pt}
⊗⊗LDX⊗FV(0:0)⊗Set rX to zero with sign of $f↓v$.\cr
\\⊗⊗DEC1⊗5\cr
⊗⊗J1N⊗*+2\cr
⊗⊗ENT1⊗0⊗Replace large difference in exponents\cr
⊗⊗SRAX⊗5,1⊗\qquad by a smaller one.\cr
\\⊗⊗ADD⊗FU⊗$\rA ← \null$difference of operands.\cr
⊗⊗JOV⊗7F⊗Fraction overflow: not $\sim $.\cr
⊗⊗CMPA⊗EPSILON(1:5)\cr
⊗⊗JG⊗8F⊗Jump if not $\sim $.\cr
⊗⊗JL⊗6F⊗Jump if $\sim $.\cr
\\⊗⊗JXZ⊗9F⊗Jump if $\sim $.\cr
⊗⊗JXP⊗1F⊗If $|\rA| = ε$, check sign of $\rA \times \rX$.\cr
\\⊗⊗JAP⊗9F⊗Jump if $\sim $. $(\rA ≠ 0)$\cr
⊗⊗JMP⊗8F\cr
\\⊗7H⊗ENTX⊗1\cr
⊗⊗SRC⊗1⊗Make rA nonzero with same sign.\cr
⊗⊗JMP⊗8F\cr
\\⊗1H⊗JAP⊗8F⊗Jump if not $\sim $. $(\rA ≠ 0)$\cr
\\⊗6H⊗ENTA⊗0\cr
⊗8H⊗CMPA⊗=0=⊗Set comparison indicator.\cr
⊗9H⊗JMP⊗*⊗Exit from subroutine.\quad\blackslug\cr}
% Vicinity of page 572
% folio 742 galley 4a 	*
\ansno 19. Let $\gamma ↓k = \delta ↓k = \eta ↓k = \sigma
↓k = 0$ for $k > n$. It suffices to find the coefficient of↔$x↓1$,
since the coefficient of $x↓k$ will be just the same except
with all subscripts increased by $k - 1$. Let $(f↓k, g↓k)$ denote
the coefficient of $x↓1$ in $(s↓k - c↓k, c↓k)$ respectively.
Then $f↓1 = (1 + \eta ↓1)(1 - \gamma ↓1 - \gamma ↓1\delta ↓1
- \gamma ↓1\sigma ↓1 - \delta ↓1\sigma ↓1 - \gamma ↓1 \delta
↓1\sigma ↓1)$, $g↓1 = (1 + \delta ↓1)(1 + \eta ↓1)(\gamma ↓1 +
\sigma ↓1 + \gamma ↓1\sigma ↓1)$, and $f↓k = (1 - \gamma ↓k\sigma
↓k - \delta ↓k\sigma ↓k - \gamma ↓k\delta ↓k\sigma ↓k)f↓{k-1}
+ (\gamma ↓k - \eta ↓k + \gamma ↓k \delta ↓k + \gamma ↓k\eta
↓k + \gamma ↓k \delta ↓k\eta ↓k + \gamma ↓k\eta ↓k\sigma ↓k
+ \delta ↓k\eta ↓k\sigma ↓k + \gamma ↓k \delta ↓k\eta ↓k\sigma
↓k)g↓{k-1}$, $g↓k = \sigma ↓k(1 + \gamma ↓k)(1 + \delta ↓k)f↓{k-1}
- (1 + \delta ↓k)(\gamma ↓k + \gamma ↓k\eta ↓k + \eta ↓k\sigma
↓k + \gamma ↓k\eta ↓k\sigma ↓k)g↓{k-1}$, for $1 < k ≤ n$. Thus
$f↓n = 1 + \eta ↓1 - \gamma ↓1 + (4n$ terms of 2nd order$) +
($higher order terms$) = 1 + \eta ↓1 - \gamma ↓1 + O(nε↑2)$ is
sufficiently small.\xskip [The Kahan summation formula was first published
in {\sl CACM \bf 8} (1965), 40; cf.\ {\sl Proc.\ IFIP Congress}
(1971), {\bf 2}, 1232. For another approach to accurate summation,
see R.↔J. \α{Hanson,} {\sl CACM \bf 18} (1975), 57--58. See also G. \α{Bohlender},
{\sl IEEE Trans.\ \bf C--26} (1977), 621--632, for algorithms that compute
round$(x↓1+\cdots+x↓n)$ and round$(x↓1\ldotsm x↓n)$ {\sl exactly}, given
$\{x↓1,\ldotss,x↓n\}$.]

\ansno 20. By the proof of Theorem↔C\null, (47) fails for $e↓w =
p$ only if $|v| + {1\over 2} ≥ |w - u| ≥ b↑{\mskip 1mu p-1} +
b↑{-1}$; hence $|f↓u| ≥ |f↓v| ≥ 1 - ({1\over 2}b - 1)b↑{-p}$.
This rather rare case, in which $|f↓w|$ before \α{normalization}
takes its maximum value 2, is necessary and sufficient for failure.

\ansno 21. (Solution by G. W. \α{Veltkamp}.)\xskip Let $c = 2↑{\lceil p/2\rceil}
+ 1$; we may assume that $p ≥ 2$, so $c$ is representable.
First compute $u↑\prime = u \otimes c$, $u↓1 = (u \ominus u↑\prime
) \oplus u↑\prime$, $u↓2 = u \ominus u↓1$; similarly, $v↑\prime = v \otimes
c$, $v↓1 = (v \ominus v↑\prime ) \oplus v↑\prime$, $v↓2 = v \ominus
v↓1$. Then set $w ← u \otimes v$, $w↑\prime ← \biglp ((u↓1 \otimes
v↓1\ominus w) \oplus (u↓1 \otimes v↓2)) \oplus (u↓2 \otimes v↓1)\bigrp
\oplus (u↓2 \otimes v↓2)$.

It suffices to prove this when $u, v > 0$ and
$e↓u = e↓u = p$, so that $u$ and $v$ are integers $\in [2↑{\mskip 1mu p-1},
2↑{\mskip 1mu p})$. Then $u = u↓1 + u↓2$ where $2↑{\mskip 1mu p-1} ≤ u↓1 ≤ 2↑{\mskip 1mu p}$, $u↓1
\mod 2↑{\lceil p/2\rceil}= 0$, and $|u↓2| ≤ 2↑{\lceil p/2\rceil-1}$;
similarly $v = v↓1 + v↓2$. The operations during the calculation
of $w↑\prime$ are exact, because $w - u↓1v↓1$ is a multiple
of $2↑{\mskip 1mu p-1}$ such that $|w - u↓1v↓1| ≤ |w - uv| + |u↓2v↓1 + u↓1v↓2
+ u↓2v↓2| ≤ 2↑{\mskip 1mu p-1} + 2↑{\mskip 1mu p+\lceil p/2\rceil}+ 2↑{\mskip 1mu p-1}$;
and similarly $|w - u↓1v↓1 - u↓1v↓2| ≤ |w - uv| + |u↓2v| < 2↑{\mskip 1mu p-1} +
2↑{\lceil p/2\rceil-1+p}$, where $w - u↓1v↓1 - u↓1v↓2$ is a multiple
of $2↑{\lceil p/2\rceil}$.

\ansno 22. We may assume that $b↑{\mskip 1mu p-1} ≤ u, v < b↑{\mskip 1mu p}$.
If $uv ≤ b↑{2p-1}$, then $x↓1 = uv - r$ where $|r| ≤ {1\over
2}b↑{\mskip 1mu p-1}$, hence $x↓2 =\hbox{round}(u - r/v) = x↓0$ (since $|r/v|
≤ {1\over 2}b↑{\mskip 1mu p-1}/b↑{\mskip 1mu p-1} ≤ {1\over 2}$, and equality implies
$v = b↑{\mskip 1mu p-1}$ hence $r = 0$). If $uv > b↑{2p-1}$, then $x↓1 =
uv - r$ where $|r| ≤ {1\over 2}b↑{\mskip 1mu p}$, hence $x↓1/v ≤ u - r/v
< b↑{\mskip 1mu p} + {1\over 2}b$ and $x↓2 ≤ b↑{\mskip 1mu p}$. If $x↓2 = b↑{\mskip 1mu p}$, then $x↓3
= x↓1$ $\biglp$for otherwise $(b↑{\mskip 1mu p} - {1\over 2})v ≤ x↓1 ≤ b↑{\mskip 1mu p}(v - 1)\bigrp$.
If $x↓2 < b↑{\mskip 1mu p}$ and $x↓1 > b↑{2p-1}$, then let $x↓2 = x↓1/v +
q$ where $|q| ≤ {1\over 2}$; we have $x↓3 =\hbox{round}(x↓1+
qv) = x↓1$. Finally if $x↓2 < b↑{\mskip 1mu p}$ and $x↓1 = b↑{2p-1}$ and
$x↓3 < b↑{2p-1}$, then $x↓4 = x↓2$ by the first case above. This
situation arises, for example, when $b = 10$, $p = 2$, $u = 19$, $v = 55$, $x↓1
= 1000$, $x↓2 = 18$, $x↓3 = 990$.

\def\omod{\hbox to 25pt{\hfill$\vcenter{\hbox{\:@\char'140}}$\hfill}\hskip-25pt
\raise .3pt\hbox to 25pt{\hfill$\vcenter{\moveleft .2pt\hbox{\:emod}}$\hfill}}
\ansno 23. Let $\lfloor u\rfloor = n$, so that
$u\omod 1 = u \ominus n = u - n + r$ where $|r| ≤ {1\over 2}b↑{-p}$;
we wish to show that round$(n - r) = n$. The result is clear
if $|n| > 1$; and $r = 0$ when $n = 0$ or 1, so the only subtle
case is when $n = -1$, $r = -{1\over 2}b↑{-p}$. The identity fails
iff $b$ is a multiple of 4 and $-b↑{-1} < u < -b↑{-2}$ and $u
\mod 2b↑{-p} = {3\over 2}b↑{-p}$ $\biglp$e.g., $p = 3$, $b = 8$,
$u = -(.0124)↓8\bigrp$.

\def\upper#1{\mathop{\hbox to 8.889pt{\:u\char'156\hskip-8.889pt\hfill
$\vcenter{\hbox{$\scriptscriptstyle#1$}}$\hfill}}}
\def\lwr#1{\mathop{\hbox to 8.889pt{\:u\char'157\hskip-8.889pt\hfill
$\vcenter{\hbox{$\scriptscriptstyle#1$}}$\hfill}}}
\ansno 24. Let $u = [u↓l, u↓r]$, $v = [v↓l, v↓r]$. Then $u \oplus v =
[u↓l\lwr+v↓l,u↓r\upper+v↓r]$,
where $x\upper+y=y\upper+x$, $x \upper+
+0 = x$ for all $x$, $x\upper+ - 0 = x$ for all
$x ≠ +0$, $x\upper+ +∞ = +∞$ for all $x≠-∞$, and
$x \upper+ -∞$ needn't be defined; $x \lwr+
y = -\biglp (-x) \upper+ (-y)\bigrp$.
If $x\oplus y$ would overflow in normal floating point arithmetic because
$x+y$ is too large, then $x\upper+y$ is $+∞$ and
$x\lwr+y$ is the largest representable number.

For subtraction, let $u \ominus v = u \oplus (-v)$, where $-v = [-v↓r, -v↓l]$.

Multiplication is somewhat more complicated. The correct procedure is to
let $$\def\\{\hss}
u \otimes v = \hbox{\:a[}\min(u↓l\\\lwr\times\\ v↓l,u↓l\\\lwr\times\\ v↓r,u↓r
\\\lwr\times\\ v↓l,u↓r\\\lwr\times\\ v↓r),\;\max(u↓l\\\upper\times\\ v↓l,
u↓l\\\upper\times\\ v↓r,u↓r\\\upper\times\\ v↓l, u↓r\\\upper\times\\ v↓r)\hbox{\:a]},$$where
$x\upper\times y=y\upper\times x$, $x\upper\times(-y)=-(x\lwr\times y)=
(-x)\upper\times y$; $x\upper\times +0=(+0$ for $x>0$, $-0$ for $x<0)$;
$x\upper\times -0=-(x\upper\times+0)$; $x\upper\times+∞=(+∞$ for
$x>+0$, $-∞$ for $x<-0)$.\xskip $\biglp$It
 is possible to determine the min and max simply
by looking at the signs of $u↓l$, $u↓r$, $v↓l$, and $v↓r$, thereby computing
only two of the eight products, except when $u↓l<0<u↓r$ and $v↓l<0<v↓r$; in the
latter case we compute four products, and the answer is $[\min(u↓l\lwr\times v↓r,
u↓r\lwr\times
v↓l),\max(u↓l\upper\times v↓l, u↓r\upper\times v↓r)]$.$\bigrp$

Finally, $u \odiv v$ is undefined if $v↓l < 0
< v↓r$; otherwise we use the formulas for multiplication with
$v↓l$ and $v↓r$ replaced respectively by $v↓r↑{-1}$ and $v↓l↑{-1}$,
 where $x \upper\times y↑{-1}=x\upper/y$,
$x\lwr\times y↑{-1}=x\lwr/y$, $(\pm0)↑{-1}=\pm∞$, $(\pm∞)↑{-1}=\pm0$.

[Cf.\  E. R. \α{Hansen,} {\sl Math.\ Comp.\ \bf22} (1968), 374--384. An alternative
scheme, in which division by 0 gives no error messages and intervals may be
neighborhoods of $∞$, has been proposed by W. M. \α{Kahan.} In Kahan's scheme, for
example, the reciprocal of $[-1,+1]$ is $[+1,-1]$, and an attempt to multiply an
interval containing 0 by an interval containing $∞$ yields $[-∞,+∞]$, the
set of all numbers. See {\sl Numerical Analysis}, Univ.\ Michigan Engineering
Summer Conf.\ Notes No.\ 6818 (1968).]

\ansno 25. Cancellation reveals {\sl previous} errors in the
computation of $u$ and $v$. For example, if $ε$ is small, we
often get poor accuracy when computing $f(x + ε) \ominus f(x)$,
because the rounded calculation of $f(x + ε)$ destroys much
of the information about $ε$. It is desirable to rewrite
\inx{cancellation errors, avoiding}
such formulas as $ε \otimes g(x, ε)$, where $g(x, ε) = \biglp
f(x + ε) - f(x)\bigrp/ε$ is first computed symbolically.
Thus, if $f(x) = x↑2$ then $g(x, ε) = 2x + ε$; if $f(x) = 
\sqrt{x}$ then $g(x, ε) = 1/(\sqrt{x
+ ε} + \sqrt{x}\,)$.

\ansno 26. See {\sl Math.\ Comp.\ \bf32} (1978), 227--232.
% Vicinity of page 574
% folio 745 galley 4b 	*
\ansbegin{4.2.3}

\ansno 1. First, $(w↓m, w↓l) = (.573,
.248)$; then $w↓mv↓l/v↓m = .290$; so the answer is $(.572, .958)$.
This in fact is the correct result to six decimals.

\ansno 2. The answer is not affected, since the normalization
routine truncates to eight places and can never look at this
particular byte position.\xskip (Scaling to the left occurs at most
once during normalization, since the inputs are normalized.)

\ansno 3. Overflow obviously cannot occur at line 09, since
we are adding two-byte quantities, or at line 22, since we are
adding four-byte quantities. In line 30 we are computing the
sum of three four-byte quantities, so this cannot overflow.
Finally, in line 32, overflow is impossible because the product
$f↓uf↓v$ must be less than unity.

\ansno 4. Insert ``\.{JOV OFLO; ENT1 0}'' between lines 03 and 04.
Replace lines 21--22 by ``\.{ADD TEMP(ABS);} \.{JNOV *+2;} \.{INC1 1}'',
and change lines 28--31 to ``\.{SLAX 5;} \.{ADD TEMP;} \.{JNOV *+2;} \.{INC1
1;} \.{ENTX 0,1;} \.{SRC 5}''. This adds five lines of code and only
1, 2, or 3 units of execution time.

\ansno 5. Insert ``\.{JOV OFLO}'' after line 06. Change lines 22,
31, 39 respectively to ``\.{SRAX 0,1}'', ``\.{SLAX 5}'', ``\.{ADD ACC}''.
Between lines
40 and 41, insert ``\.{DEC2 1;} \.{JNOV DNORM;} \.{INC2 1;} \.{INCX 1;} \.{SRC
1}''.\xskip(It's tempting to remove the ``\.{DEC2 1}'' in favor of ``\.{STZ EXPO}'',
but then ``\.{INC2 1}'' might overflow rI2!)\xskip This adds six lines of
code; the running time {\sl decreases} by $3u$, unless there is fraction
overflow, when it increases by $7u$.

\mixans 6. {⊗DOUBLE⊗STJ⊗EXITDF⊗Convert to double precision:\cr
⊗⊗ENTX⊗0⊗Clear rX.\cr
⊗⊗STA⊗TEMP\cr
\\⊗⊗LD2⊗TEMP(EXP)⊗$\rI2 ← e$.\cr
⊗⊗INC2⊗QQ-Q⊗Correct for difference in excess.\cr
\\⊗⊗STZ⊗EXPO⊗$\.{EXPO} ← 0$.\cr
⊗⊗SLAX⊗1⊗Remove exponent.\cr
⊗⊗JMP⊗DNORM⊗Normalize and exit.\cr
\noalign{\yskip}
⊗SINGLE⊗STJ⊗EXITF⊗Convert to single precision:\cr
⊗⊗JOV⊗OFLO⊗Ensure overflow is off.\cr
\\⊗⊗STA⊗TEMP\cr
⊗⊗LD2⊗TEMP(EXPD)⊗$\rI2 ← e$.\cr
⊗⊗DEC2⊗QQ-Q⊗Correct for difference in excess.\cr
\\⊗⊗SLAX⊗2⊗Remove exponent.\cr
⊗⊗JMP⊗NORM⊗Normalize, round, and exit.\quad\blackslug\cr}

\ansno 7. All three routines give zero as the answer if
and only if the exact result would be zero, so we need not worry
about zero denominators in the expressions for relative error.
The worst case of the addition routine is pretty bad: Visualized
in decimal notation, if the inputs are 1.0000000 and .99999999,
the answer is $b↑{-7}$ instead of $b↑{-8}$; thus the maximum
relative error $\delta ↓1$ is $b - 1$, where $b$ is the byte
size.

For multiplication and division, we may assume that both operands are
\inx{Operands: Quantities that are operated on; e.g., $u$ and $v$ in the
calculation of $u+v$}
positive and have the same exponent \.{QQ}.
The maximum error in multiplication is readily bounded
by considering Fig.↔4: When $uv ≥ 1/b$, we have $0 ≤ uv - u \otimes
v < 3b↑{-9} + (b - 1)b↑{-9}$, so the relative error is bounded
by $(b + 2)b↑{-8}$. When $1/b↑2 ≤ uv < 1/b$, we have $0 ≤ uv
- u \otimes v < 3b↑{-9}$, so the relative error in this case
is bounded by $3b↑{-9}/uv ≤ 3b↑{-7}$. We take $\delta ↓2$ to
be the larger of the two estimates, namely $3b↑{-7}$.

Division requires a more careful analysis of Program↔D\null.
The quantity actually computed by the subroutine is $α -
\delta - bε\biglp (α - \delta↑{\prime\prime} )(β - \delta ↑\prime )
- \delta↑{\prime\prime\prime} \bigrp - \delta ↓n$ where $α = (u↓m + εu↓l)/bv↓m$,
$β = v↓l/bv↓m$, and the nonnegative truncation errors
$(\delta , \delta ↑\prime , \delta↑{\prime\prime},
\delta↑{\prime\prime\prime})$ are respectively less than
$(b↑{-10}, b↑{-5}, b↑{-5}, b↑{-6})$; finally
$\delta ↓n$ (the truncation during
normalization) is nonnegative and less than either
$b↑{-9}$ or $b↑{-8}$, depending
on whether scaling occurs or not. The actual value of the quotient
is $α/(1 + bεβ) = α - bεαβ + b↑2αβ↑2\delta↑{\prime\prime\prime\prime}
$, where $\delta↑{\prime\prime\prime\prime}$ is the nonnegative error due
to truncation of the infinite series (2); here $\delta↑{\prime\prime\prime\prime}
< ε↑2=b↑{-10}$, since it is an alternating series. The relative error
is therefore the absolute value of $(bε\delta ↑\prime + bε\delta↑{\prime\prime}
β/α + bε\delta↑{\prime\prime\prime}/α) - (\delta /α + bε\delta ↑\prime
\delta↑{\prime\prime}/α + b↑2β↑2\delta↑{\prime\prime\prime\prime}+ \delta ↓n/α)$,
times $(1 + bεβ)$. The positive terms in this expression are
bounded by $b↑{-9} + b↑{-8} + b↑{-8}$, and the negative terms
are bounded by $b↑{-8} + b↑{-12} + b↑{-8}$ plus the contribution
by the normalizing phase, which can be about $b↑{-7}$ in magnitude.
It is therefore clear that the potentially greatest part of
the relative error comes during the normalization phase, and
that $\delta ↓3 = (b + 2)b↑{-8}$ is a safe upper bound for
the relative error.

\ansno 8. Addition: If $e↓u ≤ e↓v + 1$, the entire relative
error occurs during the normalization phase, so it is bounded
above by $b↑{-7}$. If $e↓u ≥ e↓v + 2$, and if the signs are
the same, again the entire error may be ascribed to normalization;
if the signs are opposite, the error due to shifting digits
out of the register is in the opposite direction from the subsequent
error introduced during normalization. Both of these errors
are bounded by $b↑{-7}$, hence $\delta ↓1 = b↑{-7}$.\xskip (This is
substantially better then the result in exercise↔7.)

Multiplication: An analysis as in exercise↔7 gives $\delta↓2=(b+2)b↑{-8}$.
% Vicinity of page 575
% folio 748 galley 5 	*
\ansbegin{4.2.4}

\ansno 1. Since fraction overflow can
occur only when the operands have the same sign, this is the
probability that fraction overflow occurs divided by the probability
that the operands have the same sign, namely, $7\%/\biglp{1\over 2}(91\%)\bigrp
\approx 15\%$.

\ansno 3. $\log↓{10} 2.4 - \log↓{10} 2.3 \approx 1.84834\%$.

\ansno 4. The pages would be uniformly gray (same as ``random
point on a slide rule'').

\ansno 5. The probability that $10f↓U ≤ r$ is $(r - 1)/10 +
(r - 1)/100 + \cdots = (r - 1)/9$. So in this case the leading
digits are {\sl uniformly} distributed; e.g., leading digit
1 occurs with probability ${1\over 9}$.

\ansno 6. The probability that there are three leading zero
bits is $\log↓{16} 2 = {1\over 4}$; the probability that there
are two leading zero bits is $\log↓{16} 4 - \log↓{16} 2 = {1\over
4}$; and similarly for the other two cases. The ``average'' number
of leading zero bits is 1$1\over2$, so the ``average'' number
of ``significant bits'' is $p + {1\over 2}$. The worst case,
$p - 1$ bits, occurs however with rather high probability. In
practice, it is usually necessary to base error estimates on
the worst case, since a chain of calculations is only as strong as its weakest link.
In the error analysis of Section 4.2.2, the
upper bound on relative rounding error for floating hex is $2↑{1-p}$.
In the binary case we can have $p + 1$ significant bits at all
times (cf.\ exercise 4.2.1--3), with relative rounding errors
bounded by $2↑{-1-p}$. Extensive computational experience confirms
that floating binary (even with $p$-bit precision instead of
$p + 1$) produces significantly more accurate results than $(p
+ 2)$-bit floating hex.

Tables 1 and 2 show that hexadecimal arithmetic
can be done a little faster, since fewer cycles are needed when
scaling to the right or normalizing to the left. But this fact
is insignificant compared to the substantial advantages of $b
= 2$ over other radices (cf.\ also Theorem 4.2.2C and exercises
4.2.2--13, 15,↔21), especially since floating binary can be made
as fast as floating hex with only a tiny increase in total processor
cost.

\ansno 7. For example, suppose that $\sum ↓m \biglp F(10↑{km}
\cdot 5↑k) - F(10↑{km})\bigrp = \log 5↑k/\log 10↑k$ and also that $\sum
↓m \biglp F(10↑{km} \cdot 4↑k) - F(10↑{km})\bigrp = \log 4↑k/\log
10↑k$; then
$$\chop to 9pt{\sum ↓{m}\,\biglp F(10↑{km} \cdot 5↑k) - F(10↑{km} \cdot 4↑k)\bigrp
= \log↓{10} {5\over 4}}$$
for all $k$. But now let $ε$ be a small positive
number, and choose $\delta > 0$ so that $F(x) < ε$ for $0 < x
< \delta $, and choose $M > 0$ so that $F(x) > 1-ε$ for $x
> M$. We can take $k$ so large that $10↑{-k} \cdot 5↑k < \delta$
and $4↑k > M$; hence by the monotonicity of $F$,
$$\eqalign{\sum ↓{m}\, \biglp F(10↑{km} \cdot 5↑k) - F(10↑{km} \cdot 4↑k)\bigrp
⊗ ≤ \sum ↓{m≤0}\, \biglp F(10↑{km} \cdot 5↑k) - F(10↑{k(m-1)}
\cdot 5↑k)\bigrp \cr
⊗\qquad\null + \sum ↓{m≥0}\, \biglp F(10↑{k(m+1)}
\cdot 4↑k) - F(10↑{km} \cdot 4↑k)\bigrp \cr
⊗= F(10↑{-k}5↑k) + 1 - F(10↑k4↑k) < 2ε.\cr}$$

\ansno 8. When $s > r$, $P↓0(10↑ns)$ is 1 for small $n$,
and 0 when $\lfloor 10↑ns\rfloor > \lfloor 10↑nr\rfloor $. The
least↔$n$ for which this happens may be arbitrarily large, so
no uniform bound can be given for $N↓0(ε)$ independent of $s$.\xskip
(In general, calculus textbooks prove that such a uniform bound
would imply that the limit function $S↓0(s)$ would be continuous,
and it isn't.)

\ansno 9. Let $q↓1$, $q↓2$, $\ldots$ be such that $P↓0(n) = q↓1{n-1\choose0}
+ q↓2{n-1\choose1} + \cdots$ for all $n$. It follows that
$P↓m(n) = 1↑{-m}q↓1{n-1\choose0} + 2↑{-m}q↓2{n-1\choose1}
+\cdots$ for all $m$ and $n$.

\ansno 10. When $1 < r < 10$ the generating function $C(z)$
has simple poles at the points $1 + w↓n$, where $w↓n = 2πni/\ln 10$,
hence
$$\chop to 9pt{C(z) = {\log↓{10} r - 1\over 1 - z} + \sum ↓{n≠0}
{1 + w↓n\over w↓n} {e↑{-w↓n\ln r} - 1\over (\ln 10)(z
- 1 - w↓n)} + E(z)}$$
where $E(z)$ is analytic in the entire plane. Thus
if $\theta = \hbox{arctan}(2π/\ln 10)$,
$$\eqalign{c↓m ⊗ =\log↓{10} r - 1 - {2\over \ln 10} \sum ↓{n>0}
\real\bigglp{e↑{-w↓n\ln r} - 1\over w↓n(1 + w↓n)↑m}\biggrp+ e↓m\cr
⊗= \log↓{10} r - 1 + {\sin(m\theta + 2π\log↓{10}
r) -\sin(m\theta )\over π\biglp1 + 4π↑2/(\ln 10)↑2\bigrp ↑{m/2}}
+ O\bigglp{1\over \biglp 1 + 16π↑2/(\ln 10)↑2\bigrp ↑{m/2}}\biggrp.\cr}$$

\ansno 11. When $(\log↓b U) \mod 1$ is uniformly distributed
in $[\,0, 1)$, so is $(\log↓b 1/U)\mod 1 = (1 - \log↓b U)\mod 1$.

\ansno 12. We have $h(z) = \int ↑{z}↓{1/b} f(x)\,dx\,g(z/bx)/bx + \int
↑{1}↓{z} f(x)\,dx\,g(z/x)/x$, and the same holds for $l(z) = \int ↑{z}↓{1/b} f(x)
\,dx\,l(z/bx)/bx + \int ↑{1}↓{z} f(x)\,dx\,l(z/x)/x$, hence $$
{h(z) - l(z)\over l(z)} = \int ↑{z}↓{1/b} f(x)\,dx\,{g(z/bx)
- l(z/bx)\over l(z/bx)} + \int ↑{1}↓{z} f(x)\,dx\,{g(z/x)
- l(z/x)\over l(z/x)}.$$ Since $f(x) ≥ 0$, $\hbox{\:u\char'152}
\biglp h(z) - l(z)\bigrp/l(z)\hbox{\:u\char'152}
 ≤ \int ↑{z}↓{1/b} f(x)\,dx\,A(g) + \int ↑{1}↓{z} f(x)\,dx\,A(g)$
for all $z$, hence $A(h) ≤ A(g)$. By symmetry, $A(h) ≤ A(f)$.\xskip
[{\sl Bell System Tech.\ J.\ \bf 49} (1970), 1609--1625.]

\ansno 13. Let $X = (\log↓b U)\mod 1$ and $Y = (\log↓b V)\mod
1$, so that $X$ and $Y$ are in\-de\-pend\-ently and uniformly distributed
in $[\,0, 1)$. No left shift is needed if and only if ${X + Y ≥ 1}$,
and this occurs with probability ${1\over 2}$.

(Similarly, the probability is $1\over2$ that floating point division by
Algorithm 4.2.1M needs no normalization shifts;
this needs only the weaker assumption
that both of the
operands independently have the {\sl same} distribution.)

\ansno 14. For convenience, the calculations are shown here
for $b = 10$. If $k = 0$, the probability of a carry is
$$\hbox to size{$\vcenter{
\hbox to 250pt{$\dispstyle\hfill\left(
1\over\ln 10\right)↑2\int ↓{\scriptstyle1≤x,y≤10\atop\scriptstyle x+y≥10} {dx\over
x}\,{dy\over y}.\hfill$}
\vskip 8pt
\hbox{(See Fig.\ A--7.) The value of the integral is}
\vskip 11pt
\hbox to 250pt{$\dispstyle\hfill\int↓0↑{10}{dy\over y}\int↓{10-y}↑{10}{dx\over x}
-2\int↓0↑1{dy\over y}\int↓{10-y}↑{10}{dx\over x},\hfill$}}\hfill
\vcenter{\vskip33mm
\inx{COPY PREP: Fig A-7 to be inserted}
\hbox to 32mm{\hfill\caption Fig.\ A--7.\hfill\hskip-10pt}}$}$$
and
$$\int ↑{t}↓{0}{dy\over y}\,\ln\left(1\over 1 - y/10\right)=
\int ↑{t}↓{0}\left({1\over 10} + {y\over 200}+ {y↑2\over
3000} + \cdotss\right)\,dy = {t\over 10} + {t↑2\over 400} +
{t↑3\over 9000} + \cdotss.$$
(The latter integral is essentially a ``\α{dilogarithm}.'')
Hence the probability of a carry when $k = 0$ is
$(1/\ln 10)↑2(π↑2/6 - 2 \sum ↓{n≥1} 1/n↑210↑n) = .27154$.\xskip [{\sl Note:}
When $b= 2$ and $k = 0$, fraction overflow {\sl
always} occurs, so this derivation proves that $\sum ↓{n≥1}
1/n↑22↑n = π↑2/12 - {1\over 2}(\ln 2)↑2$.]

When $k > 0$, the probability is
$$\left(1\over\ln 10\right)↑2\int ↑{10↑{1-k}}↓{10↑{-k}}\≤\≤{dy\over
y}\int ↑{10}↓{10-y}{dx\over x} = \left(1\over\ln 10\right)↑2\bigglp\sum
↓{n≥1} {1\over n↑210↑{nk}} - \sum ↓{n≥1} {1\over n↑210↑{n(k+1)}}\biggrp.$$
Thus when $b = 10$, fraction overflow should occur
with probability $.272p↓0 + .017p↓1 + .002p↓2 + \cdotss$. When
$b = 2$ the corresponding figures are $p↓0 + .655p↓1 + .288p↓2
+ .137p↓3 + .067p↓4 + \cdotss$.

Now if we use the probabilities from Table↔1,
dividing by .91 to eliminate zero operands and
assuming that the probabilities are independent of the operand
signs, we predict a probability of about 14 percent when $b
= 10$, instead of the 15 percent in exercise↔1. For $b = 2$,
we predict about 48 percent, while the table yields 44 percent.
These results are certainly in agreement within the limits of
experimental error.

\ansno 15. When $k = 0$, the leading digit is 1 if and only
if there is a carry.\xskip (It is possible for fraction overflow and
subsequent rounding to yield a leading digit of 2, when $b ≥
4$, but we are ignoring rounding in this exercise.)\xskip The probability
of fraction overflow is $.272 < \log↓{10} 2$, as shown in the
previous exercise.

When $k > 0$, the leading digit is 1 with probability
$$\left(\!{1\over\ln 10}\!\right)↑2\bigglp\int ↑{10↑{1-k}}↓{10↑{-k}}\≤\≤\≤{dy\over
y}\!\int ↓{\scriptstyle1≤x<2-y\atop\scriptstyle\hbox{\:eor }10-y≤x<10}
\≤\≤{dx\over x}\biggrp < \left(\!{1\over\ln 10}\!\right)↑2
\bigglp\int ↑{10↑{1-k}}↓{10↑{-k}}\≤\≤\≤{dy\over y}\!\int ↓{1≤x≤2}\≤{dx\over
x}\biggrp = \log↓{10} 2.$$

\ansno 16. To prove the hint [which is due to \α{Landau},
{\sl Prace matematyczno-fizyczne \bf 21} (1910), 103--113],
assume first that $\limsup a↓n = λ > 0$. Let $ε = λ/(λ + 4M)$
and choose $N$ so that $|a↓1 + \cdots + a↓n| < {1\over 10}ελn$
for all $n > N$. Let $n > N/(1 - ε)$, $n > 5/ε$ be such that $a↓n
> {1\over 2}λ$. Then, by induction, $a↓{n-k} ≥ a↓n - kM/(n - εn)
> {1\over 4}λ$ for $0 ≤ k < εn$, and $\sum ↓{n-εn<k≤n} a↓k ≥
{1\over 4}λ(εn - 1) > {1\over 5}λεn$. But $$\textstyle\left|\sum ↓{n-εn<k≤n}
a↓k\right| = \left|\sum ↓{1≤k≤n} a↓k - \sum ↓{1≤k≤n-εn} a↓k\right| ≤ {1\over
5}ελn$$ since $n - εn > N$. A similar contradiction applies if
$\liminf a↓n < 0$.

Assuming that $P↓{m+1}(n) → λ$ as $n → ∞$, let
$a↓k = P↓m(k) - λ$. If $m > 0$, the $a↓k$ satisfy the hypotheses
of the hint (cf.\ Eq.\ 4.2.2--15), 
since $0 ≤ P↓m(k)≤ 1$; hence $P↓m(n) → λ$.

\ansno 17. See {\sl Fibonacci Quarterly \bf 7} (1969), 474--475.\xskip
$\biglp$Persi \α{Diaconis} [Ph.D. thesis, Harvard University, 1974] has
shown among other things that the definition of probability
by repeated averaging is weaker than harmonic probability, in
the following precise sense: If $\lim↓{m→∞}\liminf↓{n→∞}
P↓m(n) = \lim↓{m→∞}\limsup↓{n→∞} P↓m(n) = λ$ then
the harmonic probability is $λ$. On the other hand the statement
``$10↑{k↑2}≤ n < 10↑{k↑2+k}$ for some integer
$k > 0$'' has logarithmic probability ${1\over 2}$, while repeated
averaging never settles down to give it any particular probability.$\bigrp$

\ansno 18. Let $p(a)=P(L↓a)$ and $p(a,b)=\sum↓{a≤k<b}p(k)$ for $1≤a<b$.
Since $L↓a=L↓{10a}∪L↓{10a+1}∪\cdots∪L↓{10a+9}$ for all $a$, we have
$p(a)=p\biglp10a,10(a+1)\bigrp$ by (i). Furthermore since $P(S)=P(2S)+P(2S+1)$
by (i), (ii), (iii), we have $p(a)=p\biglp2a,2(a+1)\bigrp$. It follows that
$p(a,b)=p(2↑m10↑na,2↑m10↑nb)$ for all $m,n≥0$.

If $1<b/a<b↑\prime/a↑\prime$, then $p(a,b)≤p(a↑\prime,b↑\prime)$. The reason is
that there exist integers $m$, $n$, $m↑\prime$, $n↑\prime$ such that
$2↑{m↑\prime}10↑{n↑\prime}a↑\prime≤2↑m10↑na<2↑m10↑nb≤2↑{m↑\prime}10↑{n↑\prime}
b↑\prime$ as a consequence of the fact that $\log2/\log10$ is irrational,
hence we can apply (v).\xskip
(Cf.\ exercise 3.5--22 with $k=1$ and $U↓n=n\log2/\log10$.)\xskip
In particular, $p(a)≥p(a+1)$, and it follows that $p(a,b)/p(a,b+1)≥(b-a)/(b+1-a)
$.\xskip (Cf.\ Eq.\ 4.2.2--15.)

Now we can prove that $p(a,b)=p(a↑\prime,b↑\prime)$ whenever $b/a=b↑\prime/a↑\prime
$; for $p(a,b)=p(10↑na,10↑nb)≤c↓np(10↑na,10↑nb-1)≤c↓np(a↑\prime,b↑\prime)$, for
arbitrarily large values of $n$, where
$c↓n=10↑n(b-a)\hbox{\:a/}\biglp10↑n(b-a)-1\bigrp=1+O(10↑{-n})$.

For any positive integer $n$ we have $p(a↑n,b↑n)=p(a↑n,ba↑{n-1})+p(ba↑{n-1},
b↑2a↑{n-2})+\cdots+p(b↑{n-1}a,b↑n)=np(a,b)$. If $10↑m≤a↑n≤10↑{m+1}$ and
$10↑{m↑\prime}≤b↑n≤10↑{m↑\prime+1}$, then $p(10↑{m+1},10↑{m↑\prime})≤
p(a↑n,b↑n)≤p(10↑m,10↑{m↑\prime+1})$ by (v). But $p(1,10)=1$ by (iv), hence
$p(10↑m,10↑{m↑\prime})=m↑\prime-m$ for all $m↑\prime≥m$. We conclude that
$\lfloor\log↓{10}b↑n\rfloor-\lfloor\log↓{10}a↑n\rfloor-1≤np(a,b)≤\lfloor\log↓{10}
b↑n\rfloor+\lfloor\log↓{10}a↑n\rfloor+1$ for all $n$, and $p(a,b)=\log↓{10}(b/a)$.

[This exercise was inspired by D. I. A. \α{Cohen,} who proved a slightly weaker result
in {\sl J. Combinatorial Theory} (A) {\bf20} (1976), 367--370.]
% Vicinity of page 579
% folio 754 galley 6 	*
\ansbegin{4.3.1}

\def\ansalgstep #1 #2. {\anskip\noindent\hbox to 40pt{\!
\hbox to 19pt{\hss\bf#1\ }\hfil\bf#2. }\hangindent 40pt}
\ansno 2. If the $i$th number to be
added is $u↓i = (u↓{i1}u↓{i2} \ldotsm u↓{in})↓b$, use Algorithm↔A
with step↔A2 changed to the following:

\ansalgstep{} A2\char'43. [Add digits.]
Set$$w↓j ← (u↓{1j} + \cdots + u↓{mj} + k)\mod b,\quad\hbox{and}\quad k ←
\lfloor (u↓{1j} + \cdots + u↓{mj} + k)/b\rfloor.$$

\noindent (The maximum
value of $k$ is $m - 1$, so step A3 would have to be altered
if $m > b$.)

\mixansfour 3. {⊗⊗ENT1⊗N⊗ 1\cr
⊗⊗JOV⊗OFLO⊗ 1⊗Ensure overflow is off.\cr
⊗⊗ENTA⊗0⊗ 1⊗$k ← 0$.\cr
\\⊗2H⊗ENT2⊗0⊗ N⊗$(\rI2 ≡ \hbox{next value of }k)$\cr
⊗⊗ENT3⊗M*N-N,1⊗N⊗$\biglp\.{LOC}(u↓{ij}) ≡ \.U + n(i - 1) + j\bigrp$ \cr
\\⊗3H⊗ADD⊗U,3⊗MN⊗$\rA ← \rA + u↓{ij}$.\cr
⊗⊗JNOV⊗*+2⊗MN\cr
⊗⊗INC2⊗1⊗K⊗Carry one.\cr
\\⊗⊗DEC3⊗N⊗MN⊗Repeat for $m ≥ i ≥ 0$.\cr
⊗⊗J3P⊗3B⊗MN⊗$\biglp\rI3 ≡ n(i - 1) + j\bigrp$ \cr
\\⊗⊗STA⊗W,1⊗N⊗$w↓j ←\rA$.\cr
⊗⊗ENTA⊗0,2⊗N⊗$k ← \rI2$.\cr
\\⊗⊗DEC1⊗1⊗ N\cr
⊗⊗J1P⊗2B⊗N⊗Repeat for $n ≥ j ≥ 0$.\cr
⊗⊗STA⊗W⊗ 1⊗Store final carry in $w↓0$.\quad\blackslug\cr}

\yyskip\noindent Running time, assuming that $K = {1\over 2}MN$, is $5.5MN
+ 7N + 4$ cycles.

\ansno 4. We may make the following assertion before
A1: ``$n ≥ 1$; and $0 ≤ u↓i, v↓i < b$ for $1 ≤ i ≤ n$.'' Before
A2, we assert: ``$1 ≤ j ≤ n$; $0 ≤ u↓i, v↓i < b$ for $1 ≤ i ≤
n$; $0 ≤ w↓i < b$ for $j < i ≤ n$; $0 ≤ k ≤ 1$; and
$$(u↓{j+1} \ldotsm u↓n)↓b + (v↓{j+1} \ldotsm v↓n)↓b = (kw↓{j+1}
\ldotsm w↓n)↓b.''$$
The latter statement means more precisely that
$$\chop to 12pt{\sum ↓{j<t≤n} u↓tb↑{n-t} + \sum ↓{j<t≤n} v↓tb↑{n-t} = kb↑{n-j}
+ \sum ↓{j<t≤n} w↓tb↑{n-t}.}$$
Before A3, we assert: ``$1 ≤ j ≤ n$;
$0 ≤ u↓i, v↓i < b$ for $1 ≤ i ≤ n$; $0 ≤ w↓i < b$ for $j ≤ i ≤
n$; $0 ≤ k ≤ 1$; and $(u↓j \ldotsm u↓n)↓b + (v↓j \ldotsm v↓n)↓b
= (kw↓j \ldotsm w↓n)↓b$.'' After A3, we assert that $0 ≤ w↓i
< b$ for $1 ≤ i ≤ n$; $0 ≤ w↓0 ≤ 1$; and $(u↓1 \ldotsm u↓n)↓b +
(v↓1 \ldotsm v↓n)↓b = (w↓0 \ldotsm w↓n)↓b$.

It is a simple matter to complete the proof by
verifying the necessary implications between the assertions
and by showing that the algorithm always terminates.

\ansalgstep 5. B1. Set $j ← 1$, $w↓0 ← 0$.

\ansalgstep{} B2. Set $t ← u↓j + v↓j$, $w↓j ← t \mod b$,
$i ← j$.

\ansalgstep{} B3. If $t ≥ b$, set $i ← i - 1$, $t ← w↓i
+ 1$, $w↓i ← t \mod b$, and repeat this step until $t < b$.

\ansalgstep{} B4. Increase $j$ by one, and if $j ≤ n$ go
back to B2.\quad\blackslug\lower 5pt\null

\ansalgstep 6. C1. Set $j ← 1$, $i ← 0$, $r ← 0$.

\ansalgstep{} C2. Set $t ← u↓j + v↓j$. If $t ≥ b$, set
$w↓i ← r + 1$, $w↓k ← 0$ for $i < k < j$; then set $i ← j$ and $r
← t \mod b$. Otherwise if $t < b - 1$, set $w↓i ← r$, $w↓k ← b
- 1$ for $i < k < j$; then set $i ← j$ and $r ← t$.

\ansalgstep{} C3. Increase $j$ by one. If $j ≤ n$, go
back to C2; otherwise set $w↓i ← r$, and $w↓k ← b - 1$ for $i
< k ≤ n$.\quad\blackslug\lower 5pt\null

\ansno 7. When $j = 3$, for example,
we have $k = 0$ with probability $(b + 1)/2b$; $k = 1$ with probability
$\biglp (b - 1)/2b\bigrp (1 - 1/b)$, namely the probability
that a carry occurs and that the preceding digit wasn't $b - 1$;
$k = 2$ with probability $\biglp (b - 1)/2b\bigrp (1/b)(1 - 1/b)$;
and $k = 3$ with probability $\biglp (b - 1)/2b\bigrp (1/b)(1/b)(1)$.
For fixed $k$ we may add the probabilities as $j$ varies from
1 to $n$; this gives the mean number of times the carry propagates
back $k$ places,
$$m↓k = {b - 1\over 2b↑k}\left( (n + 1 - k)\left(1
- {1\over b}\right) + {1\over b}\right).$$
As a check, we find that the average number of
carries is
$$m↓1 + 2m↓2 + \cdots + nm↓n = {1\over 2} \biggglp
n - {1\over b - 1}\bigglp 1 - \left(1\over b\right)↑n\,\biggrp\bigggrp,$$
in agreement with (6).

\def\mixanseight #1. #2{\annskip\vbox{
\halign{\hbox to 19pt{##}⊗\lft{\tt##}\quad⊗\lft{\tt##}\quad⊗\lft{\tt##}\quad
⊗$\ctr{##}$\hskip40pt⊗\lft{\tt##}\quad⊗\lft{\tt##}\quad⊗\lft{\tt##}\quad⊗$\ctr{##}
\quad$⊗##\hfill\cr
{\hfill\bf #1. }#2}}}
\mixanseight 8. {⊗⊗ENN1⊗N⊗1⊗2H⊗LDA⊗W+N+1,2⊗K\cr
⊗⊗JOV⊗OFLO⊗1⊗⊗INCA⊗1⊗K\cr
⊗⊗STZ⊗W⊗1⊗⊗STA⊗W+N+1,2⊗K\cr
⊗1H⊗LDA⊗U+N+1,1⊗N⊗⊗DEC2⊗1⊗K\cr
⊗⊗ADD⊗V+N+1,1⊗N⊗⊗JOV⊗2B⊗K\cr
⊗⊗STA⊗W+N+1,1⊗N⊗3H⊗INC2⊗1⊗N\cr
⊗⊗JNOV⊗3F⊗N⊗⊗J2N⊗1B⊗N\cr
⊗⊗ENT2⊗-1,1⊗L⊗⊗⊗⊗⊗\blackslug\cr}

\yyskip\noindent The running time depends on $L$, the number of positions
in which $u↓j + v↓j ≥ b$; and on $K$, the total number of carries.
It is not difficult to see that $K$ is the same quantity that appears in
Program↔A\null. The analysis
in the text shows that $L$ has the average value $N\biglp (b
- 1)/2b\bigrp $, and $K$ has the average value ${1\over 2}(N
- b↑{-1} - b↑{-2} - \cdots - b↑{-n})$. So if we ignore terms
of order $1/b$, the running time is $9N + L + 7K + 3 \approx
13N + 3$ cycles.

{\sl Note:} Since a carry occurs almost
half of the time, it would be more efficient to delay storing
the result by one step. This leads to a somewhat longer program
whose running time is approximately
$12N + 5$ cycles, based on the somewhat more detailed information
calculated in exercise↔7.

\ansno 9. Replace ``$b$'' by ``$b↓{n-j}$'' everywhere in step
A2.

\ansno 10. If lines 06 and 07 were interchanged, we would almost
always have overflow, but register↔A might have a negative value
at line 08, so this would not work. If the instructions on lines
05 and 06 were interchanged, the sequence of overflows occurring
in the program would be slightly different in some cases, but
the program would still be right.

\ansno 11. (a)\9 Set $j
← 1$;\xskip (b) if $u↓j < v↓j$, terminate [$u < v$]; if $u↓j = v↓j$
and $j = n$, terminate [$u = v$]; if $u↓j = v↓j$ and $j < n$,
set $j ← j + 1$ and repeat (b); if $u↓j > v↓j$, terminate
[$u > v$]. This algorithm tends to be quite fast, since there
is usually low probability that $j$ will have to get very high
before we encounter a case with $u↓j ≠ v↓j$.

\ansno 12. Use Algorithm↔S with $u↓j = 0$ and $v↓j = w↓j$. Another
``borrow'' will occur at the end of the algorithm; this
time it should be ignored.

\mixanseight 13. {⊗⊗ENTX⊗N⊗1⊗⊗ADD⊗CARRY⊗N\cr
⊗⊗JOV⊗OFLO⊗1⊗⊗JNOV⊗*+2⊗N\cr
⊗⊗ENTX⊗0⊗1⊗⊗INCX⊗1⊗K\cr
⊗2H⊗STX⊗CARRY⊗N⊗⊗STA⊗W,1⊗N\cr
⊗⊗LDA⊗U,1⊗N⊗⊗DEC1⊗1⊗N\cr
⊗⊗MUL⊗V⊗N⊗⊗J1P⊗2B⊗N\cr
⊗⊗SLC⊗5⊗N⊗⊗STX⊗W⊗1⊗\blackslug\cr}

\yyskip\noindent The running time is $23N + K + 5$ cycles, and $K$ is
roughly ${1\over 2}N$.

\ansno 14. The key inductive assertion is the one that should
be valid at the beginning of step M4; all others are readily
filled in from this one, which is as follows: ``$1 ≤ i ≤ n$;
$1 ≤ j ≤ m$; $0 ≤ u↓r < b$ for $1 ≤ r ≤ n$; $0 ≤ v↓r < b$ for $1
≤ r ≤ m$; $0 ≤ w↓r < b$ for $j < r ≤ m + n$; $0 ≤ k < b$; and
$$(w↓{j+1} \ldotsm w↓{m+n})↓b + kb↑{m+n-i-j} = u \times (v↓{j+1}
\ldotsm v↓m)↓b + (u↓{i+1} \ldotsm u↓n)↓b \times v↓jb↑{m-j}.''$$
(For the precise meaning of this notation, see the answer to exercise↔4.)

\ansno 15. The error is nonnegative and less than $(n - 2)b↑{-n-1}$.
[Similarly, if we ignore the products with $i + j > n
+ 3$, the error is bounded by $(n - 3)b↑{-n-2}$, etc.; but,
in some cases, we must compute all of the products if we want
to get the true rounded result.]

\ansalgstep 16. S1. Set $r ← 0$, $j ← 1$.

\ansalgstep{} S2. Set $w↓j ← \lfloor (rb + u↓j)/v\rfloor$,
$r ← (rb + u↓j)\mod v$.

\ansalgstep{} S3. Increase $j$ by 1, and return to S2
if $j ≤ n$.\quad\blackslug\lower 5pt\null

\ansno 17. $u/v > u↓0b↑n/(v↓1 + 1)b↑{n-1} = b\biglp 1 - 1/(v↓1
+ 1)\bigrp > b\biglp 1 - 1/(b/2)\bigrp = b - 2$.

\ansno 18. $(u↓0b + u↓1)/(v↓1 + 1) ≤ u/(v↓1 + 1)b↑{n-1} < u/v$.

\ansno 19. $u - \A qv ≤ u - \A qv↓1b↑{n-1} - \A qv↓2b↑{n-2}
=u↓2b↑{n-2}+\cdots+u↓n+\A rb↑{n-1}-\A q
v↓2b↑{n-2} < b↑{n-2}(u↓2 + 1 + \A rb - \A q
v↓2) ≤ 0$. Since $u - \A qv < 0$, $q < \A q$.

\ansno 20. If $q ≤ \A q - 2$, then $u < (\A q - 1)v
< \A q(v↓1b↑{n-1} + (v↓2 + 1)b↑{n-2}\bigrp - v < \A q
v↓1b↑{n-1} + \A qv↓2b↑{n-2} + b↑{n-1} - v ≤ \A qv↓1b↑{n-1}
+ (b\A r + u↓2)b↑{n-2} + b↑{n-1} - v = u↓0b↑n + u↓1b↑{n-1}
+ u↓2b↑{n-2} + b↑{n-1} - v ≤ u↓0b↑n + u↓1b↑{n-1} + u↓2b↑{n-2}
≤ u$. In other words, $u < u$, and this is a contradiction.

\def\bigsl{\hbox{\:a/}}
\ansno 21. (Solution by G. K. Goyal.)\xskip The inequality $v↓2\A q≤b\A r+u↓2$
implies that we have
$\A q≤(u↓0b↑2+u↓1b+u↓2)/(v↓1b+v↓2)≤u\bigsl\biglp(v↓1b+v↓2)b↑{n-2}
\bigrp$. Now $u \mod v =
u-qv = v(1-α)$ where $0≤α=q-u/v≤\A q-u/v≤u\biglp 1\bigsl\biglp(v↓1b+v↓2)b↑{n-2}
\bigrp-1/v\bigrp=u(v↓3b↑{n-3}+\cdotss)\bigsl\biglp(v↓1b+v↓2)b↑{n-2}v\bigrp
<u/(v↓1bv)≤\A q/(v↓1b)≤(b-1)/(v↓1b)$, and this is at most $2/b$ since
$v↓1≥{1\over2}(b-1)$.
% Vicinity of page 582
% folio 758 galley 7a 	*
\ansno 22. Let $u = 4100$, $v = 588$. We first try
$\A q = \lfloor {41\over 5}\rfloor = 8$, but $8 \cdot 8
> 10(41 - 40) + 0$. Then we set $\A q = 7$, and now
we find $7 \cdot 8 < 10(41 - 35) + 0$. But 7 times 588 equals↔4116,
so the true quotient is $q = 6$.\xskip (Incidentally, this example
shows that Theorem↔B cannot be improved under the given hypotheses,
when $b = 10$.)

\ansno 23. Obviously $v\lfloor b/(v + 1)\rfloor < (v + 1)\lfloor
b/(v + 1)\rfloor ≤ (v + 1)b/(v + 1) = b$; also if $v ≥ \lfloor
b/2\rfloor$ we obviously have $v\lfloor b/(v + 1)\rfloor ≥ v
≥ \lfloor b/2\rfloor $. Finally, assume that we have $1 ≤ v < \lfloor
b/2\rfloor $. Then $v\lfloor b/(v + 1)\rfloor > v\biglp b/(v
+ 1) - 1\bigrp ≥ b/2 - 1 ≥ \lfloor b/2\rfloor - 1$, be\-cause
$v\biglp b/(v + 1) - 1\bigrp - (b/2 - 1) = (b/2 - v - 1)(v - 1)/(v
+ 1) ≥ 0$. Since $v\lfloor b/(v + 1)\rfloor > \lfloor
b/2\rfloor - 1$, we must have $v\lfloor b/(v + 1)\rfloor ≥ \lfloor
b/2\rfloor $.

\ansno 24. The approximate probability is only $\log↓b 2$, not $1\over 2$.\xskip
(For example, if $b = 2↑{35}$, the probability is approximately
${1\over 35}$; this is still high enough to warrant the special
test for $d = 1$ in steps D1 and D8.)

\def\mixansfive #1. #2{\def\\{\noalign{\penalty-200}}\annskip
\halign{\hbox to 19pt{##}⊗\rt{ \it##}\quad⊗\lft{\tt##}\quad⊗\lft{\tt##}\quad
⊗\lft{\tt##}\quad⊗$\ctr{##}$⊗\quad\lft{\rm##}\cr
{\hfill\bf #1. }#2}}
\mixansfive 25. {⊗002⊗⊗ENTA⊗1⊗1\cr
⊗003⊗⊗ADD⊗V+1⊗1\cr
⊗004⊗⊗STA⊗TEMP⊗1\cr
\\⊗005⊗⊗ENTA⊗1⊗1\cr
⊗006⊗⊗JOV⊗1F⊗1⊗Jump if $v↓1 = b - 1$.\cr
\\⊗007⊗⊗ENTX⊗0⊗1\cr
⊗008⊗⊗DIV⊗TEMP⊗1⊗Otherwise compute $b/(v↓1+ 1)$.\cr
⊗009⊗⊗JOV⊗DIVBYZERO⊗1⊗Jump if $v↓1 = 0$.\cr
\\⊗010⊗1H⊗STA⊗D⊗1\cr
⊗011⊗⊗DECA⊗1⊗1\cr
\\⊗012⊗⊗JANZ⊗*+3⊗1⊗Jump if $d ≠ 1$.\cr
⊗013⊗⊗STZ⊗U⊗1 - A\cr
⊗014⊗⊗JMP⊗D2⊗1 - A\cr
\\⊗015⊗⊗ENT1⊗N⊗A⊗Multiply $v$ by $d$.\cr
⊗016⊗⊗ENTX⊗0⊗A\cr
\\⊗017⊗2H⊗STX⊗CARRY⊗AN\cr
⊗018⊗⊗LDA⊗V,1⊗AN\cr
⊗019⊗⊗MUL⊗D⊗AN\cr
⊗$\cdots$⊗⊗⊗⊗⊗(as in exercise 13)\cr
⊗026⊗⊗J1P⊗2B⊗AN\cr
\\⊗027⊗⊗ENT1⊗M+N⊗A⊗(Now $\rX = 0$.)\cr
⊗028⊗2H⊗STX⊗CARRY⊗A(M + N)⊗Multiply $u$ by $d$.\cr
⊗029⊗⊗LDA⊗U,1⊗A(M + N)\cr
⊗$\cdots$⊗⊗⊗⊗⊗(as in exercise 13)\cr
⊗037⊗⊗J1P⊗2B⊗A(M + N)\cr
⊗038⊗⊗STX⊗U⊗A⊗\quad\blackslug\lower5pt\null\cr}

\ansno 26. (See the algorithm of exercise 16.)

{\yyskip\tabskip 22pt\mixfive{\!
101⊗D8⊗LDA⊗D⊗1⊗(Remainder will be left in\cr
102⊗⊗DECA⊗1⊗1⊗\qquad locations \.{U+M+1} through \.{U+M+N})\cr
103⊗⊗JAZ⊗DONE⊗1⊗Terminate if $d = 1$.\cr
\\104⊗⊗ENN1⊗N⊗A⊗$\rI1 ≡ j - n - 1$; $j ← 1$.\cr
105⊗⊗ENTA⊗0⊗A⊗$r ← 0$.\cr
\\106⊗1H⊗LDX⊗U+M+N+1,1⊗AN⊗$\rAX ← rb+u↓{m+j}$.\cr
107⊗⊗DIV⊗D⊗AN\cr
108⊗⊗STA⊗U+M+N+1,1⊗AN\cr
109⊗⊗SLAX⊗5⊗AN⊗$r ← (rb + u↓{m+j})\mod d$.\cr
110⊗⊗INC2⊗1⊗AN⊗$j ← j + 1$.\cr
111⊗⊗J2N⊗1B⊗AN⊗Repeat for $1 ≤ j ≤ n$.\quad\blackslug\cr}}

\yyskip\noindent At this point, the division routine is complete; and
by the next exercise, register↔AX is zero.

\ansno 27. It is $du \mod dv = d(u \mod  v)$.

\ansno 28. For convenience, let us assume that $v$ has a decimal
point at the left, i.e., $v = (v↓0.v↓1v↓2\ldotsm)↓b$. After
step N1 we have ${1\over 2} ≤ v < 1 + 1/b$: for
$$\eqalignno{v\,\left\lfloor b + 1\over v↓1 + 1\right\rfloor⊗≤{v(b + 1)\over v↓1
+ 1} = {v(1 + 1/b)\over (1/b)(v↓1 + 1)} < 1 + {1\over b},\cr
\noalign{\hbox{and}}
v\,\left\lfloor b + 1\over v↓1 + 1\right\rfloor ⊗≥ {v(b+1 - v↓1)\over v↓1
+ 1} ≥ {1\over b} {v↓1(b + 1 - v↓1)\over v↓1 + 1}.\cr}$$
The latter quantity takes its smallest value when $v↓1
= 1$, since it is a convex function and the other extreme value
is greater.

The formula in step N2 may be written
$$v ← \left\lfloor b(b + 1)\over v↓1 + 1\right\rfloor{v\over b},$$
so we see as above that $v$ will never become $≥1 + 1/b$.

The minimum value of $v$ after one iteration of
step N2 is $≥$
$$\eqalign{\left(b(b + 1) - v↓1\over v↓1 + 1\right){v\over
b} ≥ \left(b(b + 1) - v↓1\over v↓1 + 1\right){v↓1\over b↑2}⊗
= \left(b(b + 1) + 1 - t\over t\right)\left(t - 1\over
b↑2\right)\cr
\noalign{\vskip3pt}
⊗= 1 + {1\over b}+{2\over b↑2} - {1\over
b↑2}\left(t + {b(b + 1) + 1\over t}\right),\cr}$$
if $t = v↓1 + 1$. The minimum of this quantity occurs
for $t = b/2 + 1$; a lower bound is $1 - 3/2b$. Hence $v↓1 ≥
b - 2$, after one iteration of step N2. Finally, we have $(1
- 3/2b)(1+1/b)↑2 > 1$, when $b ≥ 5$, so at most two more
iterations are needed. The assertion is easily verified when
$b < 5$.

\ansno 29. True, since $(u↓j \ldotsm u↓{j+n})↓b < v$.

\ansno 30. In Algorithms A and S\null, such overlap is possible if
the algorithms are rewritten slightly; e.g., in Algorithm↔A\null,
we could rewrite step A2 thus: ``Set $t ← u↓j + v↓j + k$, $w↓j
← t \mod b$, $k ← \lfloor t/b\rfloor $.''

In Algorithm M\null, $v↓j$ may be in the same location
as $w↓j$. In Algorithm↔D\null, it is most convenient (as in
Program↔D\null, exercise↔26) to let $r↓1 \ldotsm r↓n$ be the same as $u↓{m+1}
\ldotsm u↓{m+n}$; and we can also have $q↓0 \ldotsm q↓m$ the same
as $u↓0 \ldotsm u↓m$, provided that no alteration of $u↓j$ is
made in step D6.\xskip (Line 098 of Program↔D can safely be changed to ``\.{J1P
2B}'', since $u↓j$ isn't used in the subsequent calculation.)

\ansno 31. Consider the situation
of Fig.↔6 with $u = (u↓ju↓{j+1} \ldotsm u↓{j+n})↓3$ as in Algorithm↔D\null.
If the leading nonzero digits of $u$ and $v$ have the same
sign, set $r ← u - v$, $q ← 1$; otherwise set $r ← u + v$, $q ←
-1$. Now if $|r| > |u|$, or if $|r| = |u|$ and the first nonzero
digit of $u↓{j+n+1} \ldotsm u↓{m+n}$ has the same sign as the
first nonzero digit of $r$, set $q ← 0$; otherwise set $u↓j
\ldotsm u↓{j+n}$ equal to the digits of $r$.

\ansno 36. Values to 1000 decimal and 1100 octal places have
been computed by R. P. \α{Brent,} Comp.\ Centre Tech.\ Rep.\ 47 (Canberra: Australian
Nat.\ Univ., 1975).

\ansno 37. Let $d=2↑e$ so that $b>dv↓1≥b/2$. Instead of normalizing $u$ and $v$ in
step D1, simply compute the two leading digits $v↓1↑\prime v↓2↑\prime$ of
$2↑e(v↓1v↓2v↓3)↓b$ by shifting left $e$ bits. In step D3, use $(v↓1↑\prime,
v↓2↑\prime)$ instead of $(v↓1,v↓2)$ and $(u↓j↑\prime,u↓{j+1}↑\prime,
u↓{j+2}↑\prime)$ instead of $(u↓j,u↓{j+1},u↓{j+2})$, where the digits
$u↓j↑\prime u↓{j+1}↑\prime u↓{j+2}↑\prime$ are obtained from $(u↓j
u↓{j+1}u↓{j+2}u↓{j+3})↓b$ by shifting left $e$ bits. Omit division by $d$ in
step D8.\xskip (In essence, $u$ and $v$ are being ``virtually'' shifted.
This method saves computation when $m$ is small
compared to $n$.)
% Vicinity of page 584
% folio 760 galley 7b 	*

\ansbegin{4.3.2}

\ansno 1. The solution is unique since
$7 \cdot 11 \cdot 13 = 1001$. The ``constructive'' proof of Theorem↔C
tells us that the answer is $\biglp (11 \cdot 13)↑6 + 6\cdot(7 \cdot
13)↑{10} + 5 \cdot (7 \cdot 11)↑{12}\bigrp \mod 1001$. But this answer
is perhaps not explicit enough! By (23) we have $v↓1 = 1$, $v↓2
= (6 - 1) \cdot 8 \mod 11 = 7$, $v↓3 = \biglp (5 - 1) \cdot 2
- 7\bigrp \cdot 6 \mod 13 = 6$, so $u = 6 \cdot 7 \cdot 11 + 7
\cdot 7 + 1 = 512$.

\ansno 2. No. There is at most one such $u$; the additional condition
$u↓1≡\cdots≡u↓r\modulo 1$ is necessary and sufficient, and it follows that
such a generalization is not very interesting.

\ansno 3. $u ≡ u↓i\modulo{m↓i}$ implies that $u ≡ u↓i$ $\biglp$modulo
$\gcd(m↓i, m↓j)\bigrp $, so the condition $u↓i ≡ u↓j$ $\biglp$modulo
$\gcd(m↓i, m↓j)\bigrp$ must surely hold if there is a
solution. Furthermore if $u ≡ v\modulo {m↓j}$ for all $j$,
then $u - v$ is a multiple of $\lcm(m↓1, \ldotss , m↓r) = m$;
hence there is at most one solution.

The proof can now be completed in a nonconstructive
manner by counting the number of different $r$-tuples $(u↓1, \ldotss
, u↓r)$ satisfying the conditions $0 ≤ u↓j < m↓j$ and $u↓i ≡
u↓j$ $\biglp$modulo $\gcd(m↓i, m↓j)\bigrp$. If this number is
$m$, there must be a solution since \hbox{$(u \mod m↓1, \ldotss , u
\mod m↓r)$} takes on $m$ distinct values as $u$ goes from $a$
to $a + m$. Assume that $u↓1, \ldotss , u↓{r-1}$ have been chosen
satisfying the given conditions; we must now pick $u↓r ≡ u↓j$
$\biglp$modulo $\gcd(m↓j, m↓r)\bigrp$ for $1 ≤ j < r$, and by the
generalized Chinese remainder theorem for $r - 1$ elements there
are
$$\eqalign{m↓r/\!\lcm\biglp\gcd(m↓1, m↓r), \ldotss ,\gcd(m↓{r-1}, m↓r)\bigrp
⊗ = m↓r/\!\gcd\biglp\lcm(m↓1, \ldotss , m↓{r-1}), m↓r\bigrp\cr
⊗= \lcm(m↓1, \ldotss , m↓r)/\!\lcm(m↓1, \ldotss , m↓{r-1})\cr}$$
ways to do this.\xskip [This proof is based on identities
(10), (11), (12), and (14) of Section 4.5.2.]

A constructive proof [A. S. \α{Fraenkel,} {\sl Proc.\ Amer.\ Math.\ Soc.\
\bf 14} (1963), 790--791] generalizing (24) can be given
as follows. Let $M↓j = \lcm(m↓1, \ldotss , m↓j)$; we wish to
find $u = v↓rM↓{r-1} + \cdots + v↓2M↓1 + v↓1$, where $0 ≤ v↓j
< M↓j/M↓{j-1}$. Assume that $v↓1$, $\ldotss$, $v↓{j-1}$ have already
been determined; then we must solve the congruence
$$v↓jM↓{j-1} + v↓{j-1}M↓{j-2} + \cdots + v↓1 ≡ u↓j\modulo{m↓j}.$$
Here $v↓{j-1}M↓{j-2} + \cdots + v↓1 ≡ u↓i ≡ u↓j$
$\biglp$modulo $\gcd(m↓i, m↓j)\bigrp$ for $i < j$ by hypothesis,
so $c = u↓j - (v↓{j-1}M↓{j-2} + \cdots + v↓1)$ is a multiple of
$$\lcm\biglp\gcd(m↓1, m↓j), \ldotss ,\gcd(m↓{j-1},
m↓j)\bigrp = \gcd(M↓{j-1}, m↓j) = d↓j.$$
We therefore must solve $v↓jM↓{j-1} ≡ c\modulo
{m↓j}$. By Euclid's algorithm there is a number $c↓j$ such that
$c↓jM↓{j-1} ≡ d↓j\modulo {m↓j}$; hence we may take
$$v↓j = (c↓j\,c)/d↓j \mod (m↓j/d↓j).$$
Note that, as in the nonconstructive proof, we
have $m↓j/d↓j = M↓j/M↓{j-1}$.
% Vicinity of page 585
% folio 761 galley 8 	*

\ansno 4. (After $m↓4 = 91 = 7 \cdot 13$, we have
used up all products of two or more odd primes that can be less
than 100, so $m↓5$, $\ldots$ must all be prime.)
$$\baselineskip 14pt
\vbox{\halign{$m↓{#}\hfill=\null$⊗#,\qquad
⊗$m↓{#}\hfill=\null$⊗#,\qquad
⊗$m↓{#}\hfill=\null$⊗#,\qquad
⊗$m↓{#}\hfill=\null$⊗#,\qquad
⊗$m↓{#}\hfill=\null$⊗#,\cr
7⊗79⊗8⊗73⊗9⊗71⊗10⊗67⊗11⊗61\cr
12⊗59⊗13⊗53⊗14⊗47⊗15⊗43⊗16⊗41\cr
17⊗37⊗18⊗31⊗19⊗29⊗20⊗23⊗21⊗17\cr}}$$
and then we are stuck ($m↓{22} = 1$ does no good).

\ansno 5. No. The obvious upper bound,
$$3↑45↑27↑211↑1 \cdots = \prod ↓{\scriptstyle p\,\hbox{\:e odd}\atop
\scriptstyle p\,\hbox{\:e prime}}p↑{\lfloor\log↓p 100\rfloor},$$
is attained if we choose $m↓1
= 3↑4$, $m↓2 = 5↑2$, etc.\xskip (It is more difficult, however, to maximize
$m↓1 \ldotsm m↓r$ when $r$ is fixed, or to maximize $m↓1 + \cdots
+ m↓r$ as we would attempt to do when using moduli $2↑{m↓j}- 1$.)

\ansno 6. (a)\9 If $e = f + kg$, then $2↑e = 2↑f(2↑g)↑k
≡ 2↑f \cdot 1↑k \modulo {2↑g - 1}$. So if $2↑e ≡ 2↑f\modulo
{2↑g - 1}$, we have $2↑{e\mod g} ≡ 2↑{f\mod g} \modulo{2↑g -
1}$; and since the latter quantities lie between zero and $2↑g
- 1$ we must have $e \mod g = f \mod g$.\xskip (b) By part (a),
$(1 + 2↑d + \cdots + 2↑{(c-1)d}) \cdot (2↑e - 1) ≡ (1 + 2↑d
+ \cdots + 2↑{(c-1)d}) \cdot (2↑d - 1) = 2↑{cd} - 1 ≡ 2↑{ce} - 1 ≡ 2↑1 - 1 = 1
\modulo{2↑f - 1}$.

\ansno 7. $\biglp u↓j - \biglp v↓1 + m↓1(v↓2 + m↓2(v↓3
+ \cdots + m↓{j-2}v↓{j-1})\ldotsm)\bigrp\bigrp\,c↓{1j}\ldotsm c↓{(j-1)j}$

\penalty 1000
\vbox{\halign{\hbox to size{\hskip 40pt$#$}\cr
=(u↓j - v↓1)\,c↓{1j} \ldotsm
c↓{(j-1)j} - m↓1v↓2c↓{1j}\ldotsm c↓{(j-1)j} - \cdots\hfill\cr
\hfill \null-m↓1 \ldotsm m↓{j-2}v↓{j-1}c↓{1j} \ldotsm c↓{(j-1)j}\qquad\cr
\noalign{\vskip 3pt}
≡(u↓j - v↓1)\,c↓{1j} \ldotsm c↓{(j-1)j} - v↓2c↓{2j} \ldotsm c↓{(j-1)j}
- \cdots - v↓{j-1}c↓{(j-1)j}\hfill\cr
\noalign{\vskip 3pt}
= \biglp \ldotsm ((u↓j - v↓1)\,c↓{1j} - v↓2)\,c↓{2j} - \cdots
- v↓{j-1}\bigrp\,c↓{(j-1)j}\modulo {m↓j}.\hfill\cr}}

\yskip This method of rewriting the formulas uses the
same number of arithmetic operations and fewer constants; but
the number of constants is fewer only if we order the moduli
so that $m↓1 < m↓2 < \cdots < m↓r$, otherwise we would need
a table of $m↓i \mod m↓j$. This ordering of the moduli might
seem to require more computation than if we made $m↓1$ the largest,
$m↓2$ the next largest, etc., since there are many more operations
to be done modulo $m↓r$ than modulo $m↓1$; but since $v↓j$ can
be as large as $m↓j - 1$, we are better off with $m↓1 < m↓2
< \cdots < m↓r$ in (23) also. So this idea appears to be preferable
to the formulas in the text, although the formulas in the text
are advantageous when the moduli have the form (14), as shown
in Section 4.3.3.

\jpar1000000
\ansno 8. $m↓{j-1} \ldotsm m↓1v↓j ≡ m↓{j-1} \ldotsm m↓1\,\biglp
\ldotsm((u↓j - v↓1)\,c↓{1j} - v↓2)\,c↓{2j} - \cdots - v↓{j-1}\bigrp\,
c↓{(j-1)j} ≡ m↓{j-2} \ldotsm m↓1\,\biglp \ldotsm(u↓j - v↓1)\,c↓{1j}
- \cdots - v↓{j-2}\bigrp\,c↓{(j-2)j} - v↓{j-1}m↓{j-2} \ldotsm
m↓1 ≡ \cdots ≡ {u↓j - v↓1 - v↓2m↓1 - \cdots - v↓{j-1}m↓{j-2}
\ldotsm m↓1\modulo {m↓j}}$.

\jpar 2
\ansno 9. $u↓r ← \biglp (\ldotsm (v↓rm↓{r-1} + v↓{r-1})\,m↓{r-2}
+ \cdotss)\,m↓1 + v↓1\bigrp \mod m↓r$, \ $\ldotss $,

\penalty1000
\rjustline{$u↓2 ← (v↓2m↓1 + v↓1)\mod m↓2$, \ $u↓1 ← v↓1 \mod m↓1$.}
\yskip $\biglp$The computation should be done in this order,
if we want to let $u↓j$ and $v↓j$ share the same memory locations,
as they can in (23).$\bigrp$

\ansno 10. If we redefine the ``mod'' operator so that it produces
residues in the symmetrical range, the basic formulas (2), (3),
(4) for arithmetic and (23), (24) for conversion remain the
same, and the number $u$ in (24) lies in the desired range (10).
$\biglp$Here (24) is a {\sl \α{balanced mixed-radix}} notation, generalizing
``balanced ternary'' notation.$\bigrp$\xskip The comparison of two numbers
may still be done from left to right, in the simple manner described
in the text. Furthermore, it is possible to retain the value
$u↓j$ in a single computer word, if we have signed magnitude
representation within the computer, even if $m↓j$ is almost
twice the word size. But the arithmetic operations analogous
to (11) and (12) are more difficult, so it appears that on most
computers this idea would result in slightly slower operation.

\ansno 11. Multiply by
$${m + 1\over 2} = \left({m↓1 + 1\over 2}, \ldotss , {m↓r
+ 1\over 2}\right).$$
Note that $2t \cdot {m + 1\over 2} ≡ t\modulo m$.
In general if $v$ is relatively prime to $m$, then
we can find (by Euclid's algorithm) a number $v↑\prime = (v↑{\prime}↓{1},
\ldotss , v↑{\prime}↓{\hskip-.8333pt r})$ such that $vv↑\prime ≡ 1\modulo
m$; and then if $u$ is known to be a multiple of $v$ we have
$u/v = uv↑\prime $, where the latter is computed with modular
multiplication. When $v$ is not relatively prime to $m$, division
is much more difficult.

\ansno 12. Obvious from (11), if we replace $m↓j$ by $m$.\xskip
[Another way to test for overflow, if $m$ is odd, is to maintain extra
bits $u↓0=u \mod 2$ and $v↓0=v \mod 2$. Then overflow has occurred iff
$u↓0+v↓0\not≡ w↓1+\cdots+w↓r\modulo 2$, where $(w↓1,\ldotss,w↓r)$ are
the mixed-radix digits corresponding to $u+v$.]

\ansno 13. (a)\9 $x↑2 - x = (x - 1)x ≡ 0\modulo{10↑n}$ is equivalent
to $(x - 1)x ≡ 0 \modulo {p↑n}$ for $p = 2$ and 5. Either $x$
or $x - 1$ must be a multiple of $p$, and then the other is
relatively prime to $p↑n$; so either $x$ or $x - 1$ must be
a multiple of $p↑n$. If $x \mod 2↑n = x \mod 5↑n = 0$ or 1,
we must have $x \mod 10↑n = 0$ or 1; hence
automorphs have $x \mod 2↑n ≠ x \mod 5↑n$.\xskip
(b) If $x = qp↑n + r$, where $r = 0$ or 1, then $r ≡ r↑2 ≡ r↑3$,
so $3x↑2 - 2x↑3 ≡ (6qp↑nr + 3r) - (6qp↑nr + 2r) ≡ r\modulo
{p↑{2n}}$.\xskip (c) Let $c↑\prime$ be the magic constant
$\biglp 3(cx)↑2 - 2(cx)↑3\bigrp /x↑2 = 3c↑2 - 2c↑3x$.

{\sl Note:} Since the last $k$ digits of
an $n$-digit automorph form a $k$-digit automorph, it makes
sense to speak of the two $∞$-digit automorphs, $x$ and $1 - x$,
which are \α{10-adic} numbers (cf.\ exercise 4.1--31). The set of
10-adic numbers is equivalent under modular arithmetic to the set
of ordered pairs $(u↓1,u↓2)$, where $u↓1$ is a 2-adic number and $u↓2$
is a 5-adic number.
% Vicinity of page 587
% folio 763 galley 1  	*
\ansbegin{4.3.3}

{\baselineskip0pt\lineskip0pt\def\\{\lower 2.5pt\vbox to 11pt{}}
\anskip\vbox{\halign{\hbox to 19pt{#}⊗$\rt{#}$\qquad⊗$\rt{#}$\qquad⊗$\rt{#}$\qquad
⊗$\rt{#}$\cr
\bf1.\ \lower 4.5pt\vbox to 13pt{}⊗27 \times47:
⊗18 \times 42:⊗09 \times 05:⊗2718 \times 4742:\cr
\\⊗08\9\9⊗04\9\9⊗00\9\9⊗1269\9\9\9\9\cr
\\⊗08\9⊗04\9⊗00\9⊗1269\9\9\cr
\\⊗-15\9⊗+14\9⊗-45\9⊗-0045\9\9\cr
\\⊗49\9⊗16\9⊗45\9⊗0756\9\9\cr
\\⊗49⊗16⊗45⊗0756\cr
\lower 1pt\vbox to 2.4pt{}⊗\vbox{\hrule width 18pt}⊗\vbox{\hrule width 18pt}⊗
\vbox{\hrule width 18pt}⊗\vbox{\hrule width 36pt}\cr
\lower 5.5pt\vbox to 14pt{}⊗1269⊗0756⊗0045⊗12888756\cr}}}

\ansno 2. $\sqrt{Q + \lfloor \sqrt Q\rfloor
} ≤ \sqrt{Q + \sqrt Q} < 
\sqrt{Q + 2\sqrt Q + 1} = \sqrt{Q} + 1$, so $\lfloor
\sqrt{Q + R}\rfloor ≤ \lfloor \sqrt{Q}\rfloor + 1$.

\ansno 3. When $k ≤ 2$, the result is
true, so assume that $k > 2$. Let $q↓k = 2↑{Q↓k}$, $r↓k =
2↑{R↓k}$, so that $R↓k = \lfloor \sqrt{Q↓k}\rfloor$
and $Q↓k = Q↓{k-1} + R↓{k-1}$. We must show that $1 + (R↓k +
1)2↑{R↓k} ≤ 2↑{Q↓{k-1}}$; this inequality
isn't close at all, one way is to observe that $1 + (R↓k + 1)2↑{R↓k}
≤ 1 + 2↑{2R↓k}$ and $2R↓k < Q↓{k-1}$ when $k > 2$.\xskip
(The fact that $2R↓k < Q↓{k-1}$ is readily proved by induction
since $R↓{k+1} - R↓k ≤ 1$ and $Q↓k - Q↓{k-1} ≥ 2$.)

\ansno 4. For $j = 1$, $\ldotss$, $r$, calculate $U↓e(j↑2)$,
$jU↓o(j↑2)$, $V↓e(j↑2)$, $jV↓o(j↑2)$; and by recursively calling
the multiplication algorithm, calculate
$$\eqalign{W(j) ⊗= \biglp U↓e(j↑2) + jU↓o(j↑2)\bigrp
\biglp V↓e(j↑2) + jV↓o(j↑2)\bigrp ,\cr
W(-j) ⊗= \biglp U↓e(j↑2) - jU↓o(j↑2)\bigrp
\biglp V↓e(j↑2) - jV↓o(j↑2)\bigrp .\cr}$$
Then we have $W↓e(j↑2) = {1\over 2}\biglp W(j) +
W(-j)\bigrp$, $W↓o(j↑2) = {1\over 2}\biglp W(j) - W(-j)\bigrp
$. Also calculate $W↓e(0) = U(0)V(0)$. Now construct difference
tables for $W↓e$ and $W↓o$, which are polynomials whose respective
degrees are $r$ and $r - 1$.

This method reduces the size of the numbers being
handled, and reduces the number of additions and multiplications.
Its only disadvantage is a longer program (since the control
is somewhat more complex, and some of the calculations must
be done with signed numbers).

Another possibility would perhaps be
to evaluate $W↓e$ and $W↓o$ at $1↑2$, $2↑2$, $4↑2$, $\ldotss$, $(2↑r)↑2$;
although the numbers involved are larger, the calculations are
faster, since all multiplications are replaced by shifting and
all divisions are by binary numbers of the form $2↑j(2↑k - 1)$.\xskip
(Simple procedures are available for dividing by such numbers.)

\ansno 5. Start the $q$ and $r$ sequences out with $q↓0$ and
$q↓1$ large enough so that the inequality in exercise 3 is valid.
Then we will find in the formulas like those preceding
Theorem↔C that we have $\eta ↓1 → 0$ and $\eta ↓2 = \biglp 1 + 1/(2r↓k)\bigrp 2↑{1
+\sqrt{2Q↓k}-\sqrt{2Q↓{k+1}}}\,(Q↓k/Q↓{k+1})$. The factor $Q↓k/Q↓{k+1} → 1$
as $k → ∞$, so we can ignore it if we want to show that $\eta ↓2
< 1 - ε$ for all large $k$. Now $\sqrt{2Q↓{k+1}} = 
\sqrt{2Q↓k + 2\lceil\sqrt{ 2Q↓k}\,\rceil + 2} ≥ 
\sqrt{(2Q↓k + 2\sqrt{2Q↓k} + 1) + 1} ≥ \sqrt{2Q↓k} + 1 + 1/(3R↓k)$. Hence $\eta
↓2 ≤ \biglp1 + 1/(2r↓k)\bigrp2↑{-1/(3R↓k)}$, and $\lg\eta ↓2 < 0$ for
large enough $k$.

{\sl Note:} Algorithm C can also be modified to
define a sequence $q↓0$, $q↓1$, $\ldots$ of a similar type that
is based on $n$, so that $n \approx q↓k + q↓{k+1}$ after step↔C1.
This modification leads to the estimate (19).

\ansno 6. Any common divisor of
$6q + d↓1$ and $6q + d↓2$ must also divide their difference
$d↓2 - d↓1$. The $6\choose2$ differences are 2, 3, 4, 6,
8, 1, 2, 4, 6, 1, 3, 5, 2, 4, 2, so we must only show that at
most one of the given numbers is divisible by each of the primes
2, 3, 5. Clearly only $6q + 2$ is even, and only $6q + 3$ is
a multiple of 3; and there is at most one multiple of 5, since
$q↓k \neqv 3\modulo 5$.

\ansno 7. Let $p↓{k-1}<N≤p↓k$. We have
$t↓k ≤ 6t↓{k-1} + ck3↑k$ for some constant $c$; so
$t↓k/6↑k ≤ t↓{k-1}/6↑{k-1} + ck/2↑k ≤ t↓0 + c \sum ↓{j≥1}(j/2↑j)
= M$. Thus $t↓k ≤ M \cdot 6↑k=O(p↓{\!k}↑{\log↓36})$.

\ansno 8. Let $2↑k$ be the smallest power of 2 that exceeds $2K$. Set $a↓t←\omega
↑{-t↑2/2}u↓t$ and $b↓t←\omega↑{(2K-2-t)↑2/2}$, where $u↓t=0$ for $t≥K$. We want
to calculate the convolutions $c↓r=\sum↓{0≤j≤r}a↓jb↓{r-j}$ for $r=2K-2-s$, when
$0≤s<K$. The convolutions can be found by using three fast Fourier transformations
of order $2↑k$, as in the text's multiplication procedure.\xskip[Note that this
device works for any complex number $\omega$, not necessarily a root of unity.
\inx{chirp transform (exercise 8)}
\inx{evaluation of polynomials (exercise 8)}
See L. I. \α{Bluestein}, {\sl Northeast Electronics Res.\ and Eng.\ Meeting
Record \bf10} (1968), 218--219.]

\ansno 9. $\s u↓s=\A u↓{(qs)\mod K}$. In particular, if $q=-1$ we get $\A u↓{(-
r)\mod K}$, which avoids shuffling when computing \α{inverse transforms}.

\ansno 10. $A↑{[j]}(s↓{k-1},\ldotss,s↓{k-j},t↓{k-j-1},\ldotss,t↓0)$ can be written
$$\sum↓{0≤t↓{k-1},
\ldotss,t↓{k-j}≤1}\omega↑{(s↓0\ldotsm s↓{k-1})↓2\cdot(t↓{k-1}\ldotsm t↓{k-j}0\ldotsm
0)↓2}\,\,\bigglp\sum↓{0≤p<K}\omega↑{tp}u↓p\biggrp\bigglp\sum↓{0≤q<K}\omega↑{tq}v↓q\biggrp,$$
and this is $\sum↓{p,q}u↓pv↓qS(p,q)$, where $S(p,q)=0$ or $2↑j$. We have $S(p,q)=2↑j$
for exactly $2↑{2k}/2↑j$ values of $p$ and $q$.

\ansno 11. An automaton cannot have $z↓2 = 1$ until it has $c
≥ 2$, and this occurs first for $M↓j$ at time $3j - 1$. It follows
that $M↓j$ cannot have $z↓2z↓1z↓0 ≠ 000$ until time $3(j - 1)$.
Furthermore, if $M↓j$ has $z↓0 ≠ 0$ at time $t$, we cannot change
this to $z↓0 = 0$ without affecting the output; but the output
cannot be affected by this value of $z↓0$ until at least time
$t + j - 1$, so we must have $t + j - 1 ≤ 2n$. Since the first
argument we gave proves that $3(j - 1) ≤ t$, we must have $4(j
- 1) ≤ 2n$, that is, $j - 1 ≤ n/2$, i.e., $j ≤ \lfloor n/2\rfloor
+ 1$. This is the best possible bound,
since the inputs $u = v = 2↑n - 1$ require the use of $M↓j$
for all $j ≤ \lfloor n/2\rfloor + 1$.\xskip (For example, note from
Table 1 that $M↓2$ is needed to multiply two-bit numbers, at
time 3.)

\ansno 12. We can ``sweep through'' $K$ lists of \MIX-like instructions, executing
the first instruction on each list, in $O\biglp K+(N\log N)↑2\bigrp$ steps as
follows:\xskip(1) A radix list sort (Section 5.2.5) will group together all
identical instructions, in time $O(K+N)$.\xskip(2) Each set 
of $j$ identical
instructions can be performed in $O(\log N)↑2+O(j)$ steps, and there are $O(N↑2)$
sets.
A bounded number of sweeps will finish all the lists. The remaining details are
straightforward; for example, arithmetic operations can be simulated by converting
$p$ and $q$ to binary.\xskip[{\sl SIAM J. Computing}, to appear.]

\ansno 13. If it takes $T(n)$ steps to multiply
$n$-bit numbers, we can accomplish $m$-bit times
$n$-bit multiplication by breaking the $n$-bit number into $\lceil n/m\rceil$
$m$-bit groups, using $\lceil n/m\rceil T(m) + O(n + m)$ operations.
The results of this section therefore give an estimated running
time of $O(n\log m\log\log m)$ on Turing machines, or $O(n\log m)$ on machines with
random access to words of bounded size, or $O(n)$ on pointer machines.
% Vicinity of page 589
% folio 763a galley 2 Much unreadable  	*
\ansbegin{4.4}

\ansno 1. We compute $\biglp \ldotsm (a↓mb↓{m-1}
+ a↓{m-2})\,b↓{m-2} +\cdots + a↓1\bigrp \,b↓1 + a↓0$
by adding and multiplying in the $B↓j$ system.
$$\vbox{\halign{#\hfill⊗\hbox to 50pt{\hfill#\hfill}⊗\!
\hbox to 50pt{\hfill#\hfill}⊗\!
\hbox to 50pt{\hfill#\hfill}⊗\!
\hbox to 50pt{\hfill#\hfill}⊗\!
\hbox to 50pt{\hfill#\hfill}\cr
⊗T.⊗$=20($cwt.⊗$=8($st.⊗$=14($lb.⊗$=16$ oz.)))\cr
\noalign{\vskip 2pt}
Start with zero⊗0⊗0⊗0⊗\90⊗\90\cr
Add 3⊗0⊗0⊗0⊗\90⊗\93\cr
Multiply by 24⊗0⊗0⊗0⊗\94⊗\98\cr
Add 9⊗0⊗0⊗0⊗\95⊗\91\cr
Multiply by 60⊗0⊗2⊗5⊗\99⊗12\cr
Add 12⊗0⊗2⊗5⊗10⊗\98\cr
Multiply by 60⊗8⊗3⊗1⊗\90⊗\90\cr
Add 37⊗8⊗3⊗1⊗\92⊗\95\cr}}$$
(Addition and multiplication by a constant in a mixed-radix system are readily
done using a simple generalization of the usual carry rule; cf.\ exercise 4.3.1--9.)

\ansno 2. We compute $\lfloor u/B↓0\rfloor$, $\lfloor\lfloor
 u/B↓0\rfloor/B↓1\rfloor$, etc., and the remainders are $A↓0$, $A↓1$, etc.
The division is done in the $b↓j$ system.
$$\vbox{\halign{#\hfill⊗\hbox to 50pt{\hfill#\hfill}⊗\!
\hbox to 50pt{\hfill#\hfill}⊗\!
\hbox to 50pt{\hfill#\hfill}⊗\!
\hbox to 50pt{\hfill#\hfill}⊗\!
#\hfill\cr
⊗d.⊗$=24($h.⊗$=60($m.⊗$=60$ s.))\cr
\noalign{\vskip 2pt}
Start with $u$⊗3⊗9⊗12⊗37\cr
Divide by 16⊗0⊗5⊗\94⊗32⊗Remainder$\null=5$\cr
Divide by 14⊗0⊗0⊗21⊗45⊗Remainder$\null=2$\cr
Divide by 8⊗0⊗0⊗\92⊗43⊗Remainder$\null=1$\cr
Divide by 20⊗0⊗0⊗\90⊗\98⊗Remainder$\null=3$\cr
Divide by $∞$⊗0⊗0⊗\90⊗\90⊗Remainder$\null=8$\cr}}$$
{\sl Answer:} 8 T. 3 cwt. 1 st. 2 lb. 5 oz.

\ansno 3. The following procedure due to G. L. \α{Steele Jr.}\ and Jon L. \α{White}
generalizes Taranto's algorithm for $B=2$ originally published in
{\sl CACM \bf 2}, 7 (July 1959), 27.

\algstep A1. [Initialize.] Set $M←0$, $U↓0←0$.

\algstep A2. [Done?] If $u<ε$ or $u>1-ε$, go to step A4.\xskip (Otherwise no
$M$-place fraction will satisfy the given conditions.)

\algstep A3. [Transform.] Set $M←M+1$, $U↓{-M}←\lfloor Bu\rfloor$,
$u←Bu\mod1$, $ε←Bε$, and return to A2.\xskip (This transformation returns us to
essentially the same state we were in before; the remaining problem is to
convert $u$ to $U$ with fewest radix-$B$ places so that $|U-u|<ε$. Note,
however, that $ε$ may now be $≥1$; in this case we could go immediately to step
A4 instead of storing the new value of $ε$.)

\algstep A4. [Round.] If $u≥{1\over2}$, increase $U↓{-M}$ by 1.\xskip
(If $u={1\over2}$
exactly, another rounding rule such as ``increase $U↓{-M}$ by 1 only when it is
odd'' might be preferred.)\quad\blackslug

\yskip\noindent Step A4 will never increase $U↓{-M}$ from $B-1$ to $B$; for if
$U↓{-M}=B-1$ we must have $M>0$, but no $(M-1)$-place fraction was sufficiently
accurate. Steele and White
go on to consider floating-point conversions in their paper [to appear].

\ansno 4. (a)\9 $1/2↑k=5↑k/10↑k$.\xskip(b) Every prime divisor of $b$ divides $B$.

\ansno 5. Iff $10↑n-1≤c<w$, cf.\ (3).

\ansno 7. $αu≤ux≤αu+u/w≤αu+1$, hence $\lfloor αu\rfloor≤\lfloor ux\rfloor≤
\lfloorαu+1\rfloor$. Furthermore, in the special case cited we have $ux<αu+α$ and
$\lfloorαu\rfloor=\lfloorαu+α-ε\rfloor$.

\mixans 8. {⊗⊗ENT1⊗0\cr
⊗⊗LDA⊗U\cr
\\⊗1H⊗MUL⊗=1//10=\cr
\\⊗3H⊗STA⊗TEMP\cr
⊗⊗MUL⊗=-10=\cr
\\⊗⊗SLAX⊗5\cr
\\⊗⊗ADD⊗U\cr
⊗⊗JANN⊗2F\cr
\\⊗⊗LDA⊗TEMP⊗(Can occur only on\cr
⊗⊗DECA⊗1⊗\qquad the first iteration,\cr
⊗⊗JMP⊗3B⊗\qquad by exercise 7.)\cr
\\⊗2H⊗STA⊗ANSWER,1⊗(May be minus zero.)\cr
\\⊗⊗LDA⊗TEMP\cr
⊗⊗INC1⊗1\cr
⊗⊗JAP⊗1B⊗\quad\blackslug\cr}

\ansno 9. If $x↑\prime$ is an integer, $x-ε≤x↑\prime≤x$, then $(1+1/n)x-
\biglp(1+1/n)ε+1-1/n\bigrp≤x↑\prime+\lfloor x↑\prime/n\rfloor≤(1+1/n)x$.
Hence if $α$ is the binary fraction satisfying
$$1/10 - 2↑{-35} < α = (.000110011001100110011001100110011)↓2 < 1/10,$$
we find that $αu - ε ≤ v ≤ αu$ at the end of the computation, where
$$ε = \textstyle{7\over 8} + (.100010001010100011001000101010001)↓2 <
{3\over 2}.$$
Hence $u/10 - 2 < u/10 - \biglp ε + (1/10 - α)u\bigrp
≤ v ≤ αu < u/10$. Since $v$ is an integer, the proof is complete.

\ansno 10. (a)\9 Shift right one;\xskip (b) Extract left bit of each
group;\xskip (c) Shift result of (b) right two;\xskip (d) Shift result of
(c) right one, and add to result of (c);\xskip (e) Subtract result
of (d) from result of (a).

{\annskip\vbox{\baselineskip0pt\lineskip0pt
\def\dot{\hbox to 4.5pt{\hfill.\hfill}}
\def\\{\lower 2.25pt\vbox to 11pt{}}
\def\¬{$-$ \\}
\def\bar{\lower 1pt\vbox to 2.4pt{}}
\halign{\hbox to 19pt{\hfill#}⊗\hfill#⊗#\hfill\qquad⊗#\hfill\cr
\bf 11. ⊗\\⊗5\dot7\97\92\91\cr
⊗\¬⊗1\90\cr
⊗\bar⊗\vbox{\hrule width 13.5pt}\cr
⊗\\⊗4\97\dot7\92\91\cr
⊗\¬⊗\9\99\94\cr
⊗\bar⊗\vbox{\hrule width 22.5pt}\cr
⊗\\⊗3\98\93\dot2\91\cr
⊗\¬⊗\9\97\96\96\cr
⊗\bar⊗\vbox{\hrule width 31.5pt}\cr
⊗\\⊗3\90\96\96\dot1\cr
⊗\¬⊗\9\96\91\93\92\cr
⊗\bar⊗\vbox{\hrule width 40.5pt}\cr
⊗\lower 4.25pt\vbox to 13pt{}⊗2\94\95\92\99⊗\sl Answer: $(24529)↓{10}$.\cr}}}

\ansno 12. First convert the ternary number
to nonary (radix 9) notation, then proceed as in octal-to-decimal
conversion but without doubling. Decimal to \α{nonary} is similar.
In the given example, we have
$$\hbox to size{\vbox{\baselineskip0pt\lineskip0pt
\def\dot{\hbox to 4.5pt{\hfill.\hfill}}
\def\\{\lower 2.25pt\vbox to 11pt{}}
\def\¬{$-$ \\}
\def\bar{\lower 1pt\vbox to 2.4pt{}}
\halign{\hfill#⊗#\hfill⊗\qquad#\hfill\cr
\\⊗1\dot7\96\94\97\92\93\cr
\¬⊗\9\91\cr
\bar⊗\vbox{\hrule width 13.5pt}\cr
\\⊗1\96\dot6\94\97\92\93\cr
\¬⊗\9\91\96\cr
\bar⊗\vbox{\hrule width 22.5pt}\cr
\\⊗1\95\90\dot4\97\92\93\cr
\¬⊗\9\91\95\90\cr
\bar⊗\vbox{\hrule width 31.5pt}\cr
\\⊗1\93\95\94\dot7\92\93\cr
\¬⊗\9\91\93\95\94\cr
\bar⊗\vbox{\hrule width 40.5pt}\cr
\\⊗1\92\91\99\93\dot2\93\cr
\¬⊗\9\91\92\91\99\93\cr
\bar⊗\vbox{\hrule width 49.5pt}\cr
\\⊗1\90\99\97\93\99\dot3\cr
\¬⊗\9\91\90\99\97\93\99\cr
\bar⊗\vbox{\hrule width 58.5pt}\cr
\\⊗\9\99\98\97\96\95\94⊗\sl Answer: $(987654)↓{10}$.\cr}}\hfill
\vbox{\baselineskip0pt\lineskip0pt
\def\dot{\hbox to 4.5pt{\hfill.\hfill}}
\def\\{\lower 2.25pt\vbox to 11pt{}}
\def\¬{$+$ \\}
\def\bar{\lower 1pt\vbox to 2.4pt{}}
\halign{\hfill#⊗#\hfill⊗\qquad#\hfill\cr
\\⊗\9\99\dot8\97\96\95\94\cr
\¬⊗\9\9\9\99\cr
\bar⊗\vbox{\hrule width 22.5pt}\cr
\\⊗1\91\98\dot7\96\95\94\cr
\¬⊗\9\91\91\98\cr
\bar⊗\vbox{\hrule width 31.5pt}\cr
\\⊗1\93\91\96\dot6\95\94\cr
\¬⊗\9\91\93\91\96\cr
\bar⊗\vbox{\hrule width 40.5pt}\cr
\\⊗1\94\94\98\93\dot5\94\cr
\¬⊗\9\91\94\94\98\93\cr
\bar⊗\vbox{\hrule width 49.5pt}\cr
\\⊗1\96\90\94\92\98\dot4\cr
\¬⊗\9\91\96\90\94\92\98\cr
\bar⊗\vbox{\hrule width 58.5pt}\cr
\\⊗1\97\96\94\97\92\93⊗\sl Answer: $(1764723)↓9$.\cr}}}$$
% Vicinity of page 591
% folio 768 galley 3a 	*
\mixans 13. {⊗BUF⊗ALF⊗.\char'40\char'40\char'40\char'40⊗(Radix point on first
line)\cr
⊗⊗ORIG⊗*+39⊗\cr
⊗START⊗JOV⊗OFLO⊗Ensure overflow is off.\cr
⊗⊗ENT2⊗-40⊗Set buffer pointer.\cr
⊗8H⊗ENT3⊗10⊗Set loop counter.\cr
⊗1H⊗ENT1⊗$m$⊗Begin multiplication routine.\cr
⊗⊗ENTX⊗0\cr
⊗2H⊗STX⊗CARRY\cr
⊗⊗$\cdots$⊗⊗(See exercise 4.3.1--13, with\cr
⊗⊗J1P⊗2B⊗\qquad $v = 10↑9$ and $\.W = \.U$.)\cr
⊗⊗SLAX⊗5⊗$\rA ← \null$next nine digits.\cr
⊗⊗CHAR\cr
⊗⊗STA⊗BUF+40,2(2:5)⊗Store next nine digits.\cr
⊗⊗STX⊗BUF+41,2\cr
⊗⊗INC2⊗2⊗Increase buffer pointer.\cr
⊗⊗DEC3⊗1\cr
⊗⊗J3P⊗1B⊗Repeat ten times.\cr
⊗⊗OUT⊗BUF+20,2(PRINTER)\cr
⊗⊗J2N⊗8B⊗Repeat until both lines printed.\quad\blackslug\lower6pt\null\cr}

\ansno 14. Let $K(n)$ be the number of steps
required to convert an $n$-digit decimal number to binary and
at the same time to compute the binary representation of $10↑n$.
Then we have $K(2n) ≤ 2K(n) + O\biglp M(n)\bigrp$.\xskip{\sl Proof:}
Given the number $U = (u↓{2n-1} \ldotsm u↓0)↓{10}$, compute
$U↓1 = (u↓{2n-1} \ldotsm u↓n)↓{10}$ and $U↓0 = (u↓{n-1} \ldotsm
u↓0)↓{10}$ and $10↑n$, in $2K(n)$ steps, then compute $U =
10↑nU↓1 + U↓0$ and $10↑{2n} = 10↑n \cdot 10↑n$ in $O\biglp M(n)\bigrp$
steps. It follows that $K(2↑n) = O\biglp M(2↑n) + 2M(2↑{n-1})
+ 4M(2↑{n-2}) + \cdotss\bigrp = O\biglp nM(2↑n)\bigrp$.

[Similarly, \α{Sch\"onhage} has observed
that we can convert a $(2↑n\lg 10)$-bit number $U$ from binary
to decimal, in $O\biglp nM(2↑n)\bigrp$ steps. First form $V
= 10↑{2↑{n-1}}$ in $O\biglp M(2↑{n-1}) +
M(2↑{n-2}) + \cdotss\bigrp = O\biglp M(2↑n))$ steps,
then compute $U↓0 = (U\mod V)$ and $U↓1 = \lfloor U/V\rfloor$
in $O\biglp M(2↑n))$ further steps, then convert $U↓0$ and $U↓1$.]

\ansno 18. Let $U =\hbox{round}↓B(u, P)$ and $v =\hbox{round}↓b(U, p)$.
We may assume that $u ≠ 0$, so that $U ≠ 0$ and $v ≠ 0$.\xskip{\sl Case
1}, $v < u$: Determine $e$ and $E$ such that $b↑{e-1} < u
≤ b↑e$, $B↑{E-1} ≤ U < B↑E$. Then $u ≤ U+{1\over2}B↑{E-P}$ and
$U ≤ u - {1\over 2}b↑{e-p}$; hence $B↑{P-1} ≤
B↑{P-E}U < B↑{P-E}u ≤ b↑{\mskip 1mu p-e}u ≤ b↑{\mskip 1mu p}$.\xskip{\sl Case 2}, $v > u$:
Determine $e$ and $E$ such that $b↑{e-1} ≤ u < b↑e$, $B↑{E-1}
< U ≤ B↑E$. Then $u ≥ U - {1\over 2}B↑{E-P}$ and $U ≥ u + {1\over
2}b↑{e-p}$; hence $B↑{P-1} ≤ B↑{P-E}(U - B↑{E-P}) < B↑{P-E}u
≤ b↑{\mskip 1mu p-e}u < b↑{\mskip 1mu p}$. Thus we have proved that $B↑{P-1} < b↑{\mskip 1mu p}$
whenever $v ≠ u$.

Conversely, if $B↑{P-1} < b↑{\mskip 1mu p}$, the above proof
suggests that the most likely example for which $u ≠ v$ will
occur when $u$ is a power of $b$ and at the same time it is
close to a power of $B$. We have $B↑{P-1}b↑{\mskip 1mu p} < B↑{P-1}b↑{\mskip 1mu p} +
{1\over 2}b↑{\mskip 1mu p} - {1\over 2}B↑{P-1} - {1\over 4} = (B↑{P-1} +
{1\over 2}) \* (b↑{\mskip 1mu p} - {1\over 2})$; hence $1 < α = 1/(1
- {1\over 2}b↑{-p}) < 1 + {1\over 2}B↑{1-P} = β$. There are
integers $e$ and $E$ such that $\log↓B α < e\log↓B b - E <
\log↓B β$, since \α{Weyl's} theorem (exercise 3.5--22) implies that
there is an integer $e$ with $0 < \log↓B α < (e\log↓B b)\mod
1 < \log↓B β < 1$ when $\log↓B b$ is irrational. Hence $α < b↑e/B↑E
< β$, for some $e$ and $E$.\xskip (Such $e$ and $E$ may also be found
by applying the theory of continued fractions, see Section 4.5.3.)\xskip
Now we have round$↓B(b↑e, P) = B↑E$, and round$↓b(B↑E, p) <
b↑e$.\xskip [{\sl CACM \bf 11} (1968), 47--50; {\sl Proc.\ Amer.\ Math.\ Soc.\
\bf 19} (1968), 716--723.]

\ansno 19. $m↓1 = (\.{F0F0F0F0})↓{16}$, $c↓1 = 1 - 10/16$ makes $U
= \biglp (u↓7u↓6)↓{10} \ldotsm (u↓1u↓0)↓{10}\bigrp ↓{256}$; then $m↓2
= (\.{FF00FF00})↓{16}$, $c↓2 = 1 - 10↑2/16↑2$ makes
 $U = \biglp (u↓7u↓6u↓5u↓4)↓{10}(u↓3u↓2u↓1u↓0)↓{10}\bigrp
↓{65536}$; and $m↓3 = (\.{FFFF0000})↓{16}$, $c↓3 = 1 - 10↑4/16↑4$ finishes the
job.\xskip
(Cf.\ exercise 14. This technique is due to Roy A. \α{Keir,} circa 1958.)

% Vicinity of page 592
% folio 769 galley 3b 	*
\ansbegin{4.5.1}

\ansno 1. Test whether or not $uv↑\prime
< u↑\prime v$, since the denominators are positive.

\ansno 2. If $c > 1$ divides both $u/d$ and $v/d$, then $cd$
divides both $u$ and $v$.

\ansno 3. Let $p$ be prime. If $p↑e$ is a divisor
of $uv$ and $u↑\prime v↑\prime$ for $e ≥ 1$, then either $p↑e\rslash
u$ and $p↑e\rslash v↑\prime$ or $p↑e\rslash u↑\prime$ and $p↑e\rslash
v$; hence $p↑e\rslash\gcd(u, v↑\prime )\gcd(u↑\prime , v)$.
The converse follows by reversing the argument.

\ansno 4. Let $d↓1 =\ gcd(u, v)$, $d↓2 =\gcd(u↑\prime , v↑\prime
)$; the answer is $w = (u/d↓1)(v↑\prime /d↓2)\hbox{sign}(v)$, $w↑\prime
= |(u↑\prime /d↓2)(v/d↓1)|$, with a ``divide by zero'' error
message if $v = 0$.

\ansno 5. $d↓1 = 10$, $t = 17 \cdot 7 - 27 \cdot
12 = -205$, $d↓2 = 5$, $w = -41$, $w↑\prime = 168$.

\ansno 6. Let $u↑{\prime\prime} = u↑\prime /d↓1$, $v↑{\prime\prime}
= v↑\prime /d↓1$; our goal is to show that $\gcd(uv↑{\prime\prime} + u↑{\prime\prime}
v,d↓1)={\gcd(uv↑{\prime\prime}+u↑{\prime\prime}v,d↓1u↑{\prime\prime}v↑{\prime\prime}
)}$. If $p$ is a prime that divides $u↑{\prime\prime} $, then $p$ does
not divide $u$ or↔$v↑{\prime\prime} $, so $p$ does not divide $uv↑{\prime\prime}
+ u↑{\prime\prime} v$. A similar argument holds for prime divisors 
of↔$v↑{\prime\prime} $, so no prime divisors of $u↑{\prime\prime} v↑{\prime\prime}$
affect the given gcd.

\ansno 7. $(N - 1)↑2 + (N - 2)↑2 = 2N↑2 - (6N - 5)$. If the
inputs are $n$-bit binary numbers, $2n + 1$ bits may be necessary
to represent $t$.

\ansno 8. For multiplication and division these quantities
obey the rules $x/0 =\hbox{sign}(x)∞$, $(\pm ∞) \times x = x \times
(\pm ∞) = (\pm ∞)/x = \pm\hbox{sign}(x)∞$, $x/(\pm ∞) = 0$, provided
that $x$ is finite and nonzero, without change to the algorithms
described. Furthermore, the algorithms can readily be modified
so that $0/0 = 0 \times (\pm ∞) = (\pm ∞) \times 0 = \hbox{``}(0/0)$'',
where the latter is a representation of ``undefined''; and so
that if either operand is ``undefined'' the result will be ``undefined''
also. 

Since the multiplication and division subroutines can
yield these fairly natural rules of ``\α{extended arithmetic},''
it is sometimes worthwhile to modify the addition and subtraction
operations so that they satisfy the rules $x \pm ∞ = \pm ∞$,
$x \pm (-∞) = \mp ∞$, for $x$ finite; $(\pm ∞) + (\pm ∞) = \pm
∞ - (\mp ∞) = \pm ∞$; furthermore $(\pm ∞) + (\mp ∞) = (\pm∞) - (\pm ∞) = (0/0)$;
and if either or both operands are $(0/0)$, the result should also be
$(0/0)$. Equality
tests and comparisons may be treated in a similar manner.

The above remarks are independent of ``overflow''
indications. If $∞$ is being used to suggest overflow, it is incorrect
to let $1/∞$ be equal to zero,
lest inaccurate results be regarded as true answers. It is far
better to represent overflow by $(0/0)$, and to adhere to the convention
that the result of any operation is undefined if at least one
of the inputs is undefined. This type of overflow indication
has the advantage that final results of an extended calculation
reveal exactly which answers are defined and which are not.

\ansno 9. If $u/u↑\prime ≠ v/v↑\prime $, then
$$1 ≤ |uv↑\prime - u↑\prime v| = u↑\prime v↑\prime |(u/u↑\prime
) - (v/v↑\prime )| < |2↑{2n}(u/u↑\prime ) - 2↑{2n}(v/v↑\prime)|;$$
two quantities differing by more than unity cannot
have the same ``floor.'' $\biglp$In other words, the first $2n$
bits to the right of the binary point are enough to characterize
the value of the fraction, when there are $n$-bit denominators.
We cannot improve this to $2n - 1$ bits, for if $n = 4$ we have
${1\over 13} = (.00010011\ldotsm)↓2$, ${1\over 14} = (.00010010
\ldotsm)↓2$.$\bigrp$

\ansno 11. To divide by $(v + v↑\prime \sqrt{5}\,)/v↑{\prime\prime} $,
when $v$ and $v↑\prime$ are not both zero, multiply by the reciprocal,
$(v-v↑\prime\sqrt5\,)v↑{\prime\prime}/(v↑2-5v↑{\prime2})$, and reduce
to lowest terms.

\ansno 12. One idea is to limit numerator and denominator to a total of
27 bits, where we need only store 26 of these bits (since the leading bit
of the denominator can be assumed↔1). This leaves room for a sign and five
bits to indicate the denominator size. Another idea is to use 28 bits for
numerator and denominator, which are to have a total of at most seven
\α{hexadecimal} digits, together with a sign and a 3-bit field to indicate
the number of hexadecimal digits in the denominator.

[Using the formulas in the next exercise, the first alternative leads to exactly
2140040119 finite representable numbers, while the second leads to
1830986459. The first alternative is preferable because it
represents more values, and because it is `cleaner' and makes smoother
transitions between ranges.]

\ansno 13. The number of multiples of $n$ in the interval $(a,b\,]$ is
$\lfloor n/a\rfloor-\lfloor a/n\rfloor$. Hence, by \α{inclusion and exclusion},
the answer to this problem is $S↓0-S↓1+S↓2-\cdotss$, where $S↓k$ is
$\sum\lfloor M/P\rfloor\biglp{\lfloor N↓2/P\rfloor-\lfloor N↓1/P\rfloor}\bigrp$,
summed over all products $P$ of $k$ distinct primes.
% Vicinity of page 593
% folio 770 galley 4 	*
\ansbegin{4.5.2}

\ansno 1. Substitute min, max, + consistently
for gcd, lcm, $\times$, respectively.

\ansno 2. For prime $p$, let $u↓p$, $v↓{1p}$, $\ldotss$, $v↓{np}$
be the exponents of $p$ in the canonical factorizations of $u$,
$v↓1$, $\ldotss$, $v↓n$. By hypothesis, $u↓p ≤ v↓{1p} +\cdots
+ v↓{np}$. We must show that $u↓p ≤ \min(u↓p, v↓{1p})
+\cdots + \min(u↓p, v↓{np})$, and this is certainly
true if $u↓p$ is greater than or equal to each $v↓{jp}$, or
if $u↓p$ is less than some $v↓{jp}$.

\ansno 3. {\sl Solution 1:} A one-to-one correspondence
is obtained if we set $u = \gcd(d, n)$ and $v = n↑2/\lcm(d, n)$
for each divisor $d$ of $n↑2$.\xskip {\sl Solution 2:} If $n = p↑{e↓1}↓1
\ldotss p↑{e↓r}↓r$, the number in each case is $(2e↓1 + 1)
\ldotsm (2e↓r + 1)$.

\ansno 4. See exercise 3.2.1.2--15(a).

\ansno 5. Shift $u$ and $v$ right until neither is a
multiple of 3, remembering the proper power of 3 that will appear in the gcd.
Each subsequent iteration sets $t ← u + v$ or $t ← u - v$
(whichever is a multiple of 3), shifts $t$ right until
it is not a multiple of 3, then replaces $\max(u, v)$ by the
result.
$$\vbox{\halign{\hfill#⊗\qquad\hfill#⊗\qquad#\hfill\cr
$u$\hfill⊗$v$\hfill⊗\hfill$t$\qquad\cr
\noalign{\vskip 3pt}
13634⊗24140⊗10506, 3502;\cr
13634⊗3502⊗17136, 5712, 1904;\cr
1904⊗3502⊗5406, 1802;\cr
1904⊗1802⊗102, 34;\cr
34⊗1802⊗1836, 612, 204, 68;\cr
34⊗68⊗102, 34;\cr
34⊗34⊗0.\cr}}$$
The evidence that $\gcd(40902,24140)=34$ is now overwhelming.

\ansno 6. The probability that both $u$ and
$v$ are even is ${1\over 4}$; the probability that both are
multiples of four is ${1\over 16}$; etc. Thus $A$ has the distribution
given by the generating function
$${3\over 4} + {3\over 16}z + {3\over 64}z↑2 +\cdots
 = {3/4\over1 - z/4}.$$
The mean is ${1\over 3}$, and the standard deviation
is $\sqrt{\,{2\over 9} + {1\over 3} - {1\over 9}} = {2\over
3}$. If $u$ and $v$ are independently and uniformly distributed with
$1 ≤ u, v < 2↑N$, then some small correction terms are needed;
the mean is then actually
$$\chop to 11pt{(2↑N - 1)↑{-2} \sum ↓{1≤k≤N}(2↑{N-k} - 1)↑2 = {\textstyle{1\over
3}}-{\textstyle{4\over 3}}(2↑N - 1)↑{-1} + N(2↑N - 1)↑{-2}.}$$

\ansno 7. When $u, v$ are not both even, each of
the cases (even, odd), (odd, even), (odd, odd) is equally probable,
and $B = 1$, 0, 0 in these cases. Hence $B = {1\over 3}$ on
the average. Actually, as in exercise 6, a small correction
could be given to be strictly accurate when $1 ≤ u, v < 2↑N$;
the probability that $B = 1$ is actually
$$\chop to 11pt{(2↑N - 1)↑{-2}\sum ↓{1≤k≤N}(2↑{N-k} - 1)2↑{N-k} = {\textstyle{1\over
3}} - {\textstyle{1\over 3}}(2↑N - 1)↑{-1}.}$$

\ansno 8. The quantity $E$ is the number of subtraction cycles
in which $u > v$, plus one if $u$ is odd after step B1. If we
change the inputs from $(u, v)$ to $(v, u)$, the value of $C$
stays unchanged, while $E$ becomes $C - E$ or $C - E - 1$; the
latter case occurs iff $u$ and $v$ are both odd after step B1,
and this has probability ${1\over 3} + {2\over 3}/(2↑N -
1)$. Hence \def\\{↓{\hbox{\:e ave}}}
$$\textstyle E\\ = C\\ - E\\ - {1\over 3} - {2\over
3}/(2↑N - 1).$$

\ansno 9. The binary algorithm first gets to B6
with $u = 1963$, $v = 1359$; then $t ← 604$, 302, 151, etc. The
gcd is 302. Using Algorithm X we find that $2 \cdot 31408 - 23
\cdot 2718 = 302$.

\ansno 10. (a)\9 Two integers are relatively prime iff they are
not both divisible by any prime number.\xskip (b) Rearrangement of
the sum in (a), in terms of the denominators $k = p↓1 \ldotsm
p↓r$.\xskip $\biglp$Note
that each of the sums in (a) and (b) is actually finite.$\bigrp$\xskip
(c) Since $(n/k)↑2 - \lfloor n/k\rfloor ↑2 = O(n/k)$, we have $q↓n - \sum
↓{1≤k≤n\lower2pt\null} \mu (k)(n/k)↑2 = \sum ↓{1≤k≤n} O(n/k) = O(nH↓n)$.
Furthermore $\sum↓{k>n}(n/k)↑2=O(n)$.\xskip (d)
$\sum ↓{d\rslash n} \mu (d) = \delta ↓{1n}$.\xskip [In fact, we have
the more general result
$$\sum ↓{d\rslash n} \mu (d)\left(n\over d\right)↑s = n↑s - \sum
\left(n\over p\right)↑s +\sum\left(n\over pq\right)↑s-\cdotss,$$
as in part (b), where the sums on the right are over the prime
divisors of $n$, and this is equal to $n↑s(1 - 1/p↑{s}↓{1}) \ldotsm
(1 - 1/p↑{s}↓{r})$ if $n = p↑{e↓1}↓{1} \ldotss p↑{e↓r}↓{r}$.]

{\sl Notes:} Similarly, we find that a set of $k$ integers is relatively prime with
probability $1\hbox{\:a/}\biglp\sum↓{n≥1}1/n↑k\bigrp$. This proof
of Theorem D is due to F. \α{Mertens},
{\sl J. f\"ur die reine und angew.\ Math.\ \bf 77}
(1874), 289--291. The technique actually gives a much stronger result,
namely that $6π↑{-2}mn + O(n\log m)$ pairs of integers $u\in\hbox{\:a[}
f(m), f(m) + m\bigrp$, $v \in \hbox{\:a[} g(n), g(n) +
n\bigrp$ are relatively prime, for arbitrary $f$
and $g$, when $m≤n$.

\ansno 11. (a)\9 $6/π↑2$ times $1 + {1\over 4} + {1\over 9}$,
namely $49/(6π↑2) \approx .82746$.\xskip (b) $6/π↑2$ times 1$/1 + 2/4
+ 3/9 +\cdotss$, namely $∞$.\xskip $\biglp$This is true in spite of the
result of exercise 12, and in spite of the fact that the average
value of $\ln\gcd(u, v)$ is a small, finite number.$\bigrp$

\ansno 12. Let $\sigma (n)$ be the number
of positive divisors of $n$. The answer is
$$\sum ↓{k≥1}\,\sigma (k) \cdot {6\over π↑2k↑2} = {6\over π↑2}
\bigglp\sum ↓{k≥1} {1\over k↑2}\biggrp
↑2 = {π↑2\over 6} .$$
[Thus, the average is {\sl less} than 2, although
there are always at least two common divisors when $u$ and $v$ are
not relatively prime.]

% Vicinity of page 595
% folio 771 galley 5 	*
\ansno 13. $1 + {1\over 9} + {1\over 25} +\cdots
= 1 + {1\over 4} + {1\over 9} +\cdots - {1\over
4}(1 + {1\over 4} + {1\over 9} +\cdotss)$.

\ansno 14. $v↓1 = \pm v/u↓3$, $v↓2 =\mp u/u↓3$ (the sign depends
on whether the number of iterations is even or odd). This follows
from the fact that $v↓1$ and $v↓2$ are relatively prime to each
other (throughout the algorithm), and that $v↓1u = -v↓2v$.\xskip [Hence
$v↓1u =\lcm(u, v)$ at the close of the algorithm, but this
is not an especially efficient way to compute the \α{least common
multiple}. For a generalization, see exercise 4.6.1--18.]

G. E. \α{Collins} has observed that $|u↓1| ≤ {1\over
2}v/u↓3$, $|u↓2| ≤ {1\over 2}u/u↓3$, at the termination of Algorithm
X\null, except in certain trivial cases, since the final value of
$q$ is usually $≥2$. This bounds the size of $|u↓1|$ and $|u↓2|$ throughout
the execution of the algorithm.

\ansno 15. Apply Algorithm X to $v$ and $m$, thus obtaining
a value $x$ such that $xv ≡ 1\modulo m$.\xskip (This can be done
by simplifying Algorithm X so that $u↓2$, $v↓2$, and $t↓2$ are not computed,
since they are never used in the answer.)\xskip Then set $w ← ux
\mod m$.\xskip [It follows, as in exercise 30, that this process requires
$O(n↑2)$ units of time, when it is applied to large $n$-bit
numbers. An alternative to Algorithm X appears in exercise 35.]

\ansno 16. (a)\9 Set $t↓1 = x + 2y + 3z$; then $3t↓1 + y + 2z
= 1$, $5t↓1 - 3y - 20z = 3$. Eliminate↔$y$, then $14t↓1 - 14z
= 6$: No solution.\xskip (b) This time $14t↓1 - 14z = 0$. Divide by
14, eliminate $t↓1$; the general solution is $x = 8z - 2$, $y
= 1 - 5z$, $z$ arbitrary.

\ansno 17. Let $u↓1$, $u↓2$, $u↓3$, $v↓1$, $v↓2$, $v↓3$ be multiprecision
variables, in addition to $u$ and $v$. The extended algorithm will
act the same on $u↓3$ and $v↓3$ as Algorithm L does on $u$ and
$v$. New multiprecision operations are to set $t ← Au↓j$, $t ←
t + Bv↓j$, $w ← Cu↓j$, $w ← w + Dv↓j$, $u↓j ← t$, $v↓j ← w$ for all
$j$, in step L4; also if $B = 0$ in that step to set $t ← u↓j
- qv↓j$, $u↓j ← v↓j$, $v↓j ← t$ for all $j$ and for $q = \lfloor
u↓3/v↓3\rfloor $. A similar modification is made to step L1
if $v↓3$ is small. The inner loop (steps L2 and L3) is unchanged.

\ansno 18. If $mn = 0$, the probabilities of the lattice-point
\inx{brute force}
model in the test are exact, so we may assume that $m ≥ n >
0$. {\sl Valida vi}, the following values have been obtained:

\yskip{\sl Case 1}, $m = n$.\xskip From $(n, n)$ we go to $(n
- t, n)$ with probability $t/2↑t - 5/2↑{t+1} + 3/2↑{2t}$, for
$2 ≤ t < n$.\xskip (These values are ${1\over 16}$, ${7\over 64}$,
${27\over 256}$, $\ldotss\,$.)\xskip To $(0, n)$ the probability is $n/2↑{n-1}
- 1/2↑n + 1/2↑{2n-2}$. To $(n, k)$ the probability is the same
as to $(k, n)$. The algorithm terminates with probability $1/2↑{n-1}$.

\yskip{\sl Case 2}, $m = n + 1$.\xskip From $(n + 1,
n)$ we get to $(n, n)$ with probability ${1\over 8}$ when $n
> 1$, or 0 when $n = 1$; to $(n - t, n)$ with probability $11/2↑{t+3}
- 3/2↑{2t+1}$, for $1 ≤ t < n - 1$.\xskip (These values are ${5\over
16}$, ${1\over 4}$, $\ldotss\,$.)\xskip We get to $(1, n)$ with probability
$5/2↑{n+1} - 3/2↑{2n-1}$, for $n > 1$; to $(0, n)$ with probability
$3/2↑n - 1/2↑{2n-1}$.

\yskip{\sl Case 3}, $m ≥ n + 2$.\xskip The probabilities are
given by the following table:
$$\vbox{\baselineskip13pt
\halign{$#:\hfill$\qquad⊗$#\hfill$\cr
(m - 1, n)⊗1/2 - 3/2↑{m-n+2} - \delta ↓{n1}/2↑{m+1};\cr
(m - t, n)⊗1/2↑t + 3/2↑{m-n+t+1},\qquad 1 < t < n;\cr
(m - n, n)⊗1/2↑n + 1/2↑m,\qquad n > 1;\cr
(m - n - 1, n)⊗1/2↑{n+1} + 1/2↑{m-1};\cr
(m - n - t, n)⊗1/2↑{n+t},\qquad 1 < t < m - n;\cr
(0, n)⊗1/2↑{m-1}.\cr}}$$

\yskip{\sl Note:} Although these exact probabilities
will certainly improve on the lattice-point model considered
in the text, they lead to recurrence relations of much greater
complexity; and they will not provide the true behavior of Algorithm
B\null, since for example the probability that $\gcd(u, v) = 5$ is
different from the probability that $\gcd(u, v) = 7$.

\ansno 19. $A↓{n+1} = a + \sum ↓{1≤k≤n} 2↑{-k}A↓{(n+1)(n-k)}
+ 2↑{-n}b = a + \sum ↓{1≤k≤n} 2↑{-k}A↓{n(n-k)} + {1\over 2}c{(1
- 2↑{-n})} + 2↑{-n}b = a + {1\over 2}A↓{n(n-1)} + {1\over 2}(A↓n - a) + {1\over
2}c(1 - 2↑{-n})$;
now substitute for $A↓{n(n-1)}$ from (36).

\ansno 20. The paths described in the hint have the same probability,
but the subsequent termination of the algorithm has a different
probability; thus $λ = k + 1$ with probability $2↑{-k}$ times
the probability that $λ = 1$. Let the latter probability be
$p$. We know from the text that $λ = 0$ with probability
$\approx{3\over 5}$; hence ${2\over 5} \approx p(1 + {1\over 2} + {1\over
4} + \cdotss) = 2p$. The average is $p(1
+ {2\over 2} + {3\over 4} + {4\over 8} +\cdotss)
= p(1 + {1\over 2} + {1\over 4} + {1\over 8} +\cdotss
)↑2 = 4p$.\xskip [The exact probability that $λ = 1$ is ${1\over 5}
- {6\over 5}(-{1\over 4})↑n$ if $m > n ≥ 1$, ${1\over 5}
- {16\over 5}(-{1\over 4})↑n$ if $m = n ≥ 2$.]

\ansno 21. Show that for fixed $v$ and for $2↑m < u < 2↑{m+1}$,
when $m$ is large, each subtraction-shift cycle of the algorithm
reduces $\lfloor\lg u\rfloor$ by two, on the average.

\ansno 22. Exactly $(N - m)2↑{m-1+\delta↓{m0}}$ integers
$u$ in the range $1 ≤ u < 2↑N$ have $\lfloor\lg u\rfloor = m$,
after $u$ has been shifted right until it is odd.

\ansno 23. The first sum is $2↑{2N-2} \sum ↓{0≤m<n<N} mn2↑{-m-n}\biglp
(α + β)N + \gamma - αm - βn\bigrp $. Since $$\chop to 6pt{\sum ↓{0≤m<n} m2↑{-m}=2
- (n+ 1)2↑{1-n}}$$ and $$\sum ↓{0≤m<n} m(m - 1)2↑{-m} = 4 - (n↑2
+ n + 2)2↑{1-n},$$ the sum on $m$ is
$$\baselineskip14pt
\vbox{\halign{\hbox to size{$\dispstyle#$}\cr
\quad 2↑{2N-2} \sum ↓{0≤n<N}
n2↑{-n}\biglp (\gamma - α + (α + β)N)(2 - (n + 1)2↑{1-n})\hfill\cr
\hfill\null - α(4
- (n↑2 + n + 2)2↑{1-n}) - βn\bigrp\quad\cr
\noalign{\vskip 8pt}
\hfill = 2↑{2N-2}\biglp (α + β)N
\sum ↓{0≤n<N} n2↑{-n}(2 - (n + 1)2↑{1-n}) + O(1)\bigrp.\hfill\cr}}$$Thus
the coefficient of $(α + β)N$ in the answer is found to be $2↑{-2}\biglp
4 - ({4\over 3})↑3\bigrp = {11\over 27}$. A similar argument
applies to the other sum.

{\sl Note:} The {\sl exact} value of the
sums may be obtained after some tedious calculation by means
of the general formula
$$\sum ↓{0≤k<n}k↑{\underline m}\,z↑k = {m!\,z↑m\over (1 - z)↑{m+1}} - \sum ↓{0≤k≤m}
{m↑{\underline k}\,n↑{\underline{m-k}}\,z↑{n+k}\over (1 - z)↑{k+1}},$$
\inx{summation by parts}
\inx{factorial powers}
which follows from summation by parts.

\ansno 24. Solving a recurrence similar to (34), we find
that the number of times is $A↓{mn}$, where $A↓{00} = 1$, $A↓{0n}
= (n + 3)/2$, $A↓{nn} = {8\over 5} - (3n + 13)/(9 \cdot 2↑n) +
{128\over 45}(-{1\over 4})↑n$ if $n ≥ 1$, $A↓{mn} = {8\over5}-2/(3\cdot2↑n)+
{16\over 15}(-{1\over4})↑n$ if $m > n ≥ 1$. Since the condition $u = 1$ or $v = 1$
is therefore satisfied only about 1.6 times in an average run,
it is not worth making the suggested test each time step B5
is performed.\xskip (Of course the lattice model is not completely
accurate, but it seems reasonable to believe that it is not
too inaccurate for this application.)

\baselineskip 12pt
\ansno 25. (a)\9 $F↓{n+1}(x)=\sum↓{d≥1}2↑{-d}\,\hbox{probability that }\biglp X↓n<1$
and $2↑d/(X↑{-1}↓{n} - 1) < x$ or $X↓n > 1$ and $(X↓n - 1)/2↑d
< x\bigrp = \sum ↓{d≥1} 2↑{-d}\biglp F↓n(1/(1 + 2↑dx↑{-1}))
+ F↓n(1 + 2↑dx) - F↓n(1)\bigrp $.\xskip (b) $G↓{n+1}(x) = 1 - \sum
↓{d≥1}2↑{-d}\biglp G↓n(1/(1 + 2↑dx)) - G↓n(1/(1 + 2↑dx↑{-1}))\bigrp
$.\xskip (c) $H↓n(x)=\sum↓{d≥1}2↑{-d}\,\hbox{probability that }\biglp Y↓n ≤ x$ and
$(1 - Y↓n)/2↑d ≤ x\bigrp$ can be transformed into
$\sum ↓{d≥1} 2↑{-d}\max\biglp 0,G↓n(x) - G↓n(1 - 2↑dx)\bigrp $.

\baselineskip 11pt\yskip
Starting with $G↓0(x) = x$ we get rapid convergence
to a limiting distribution where $$\biglp G(.1), \ldotss , G(.9)\bigrp
= (.2750, .4346, .5544, .6507, .7310, .7995, .8590, .9114, .9581).$$
The expected value of $\ln\biglp\max(u↓n,v↓n)/\!\max(u↓{n+1},
v↓{n+1})\bigrp$ is $\int ↑{1}↓{0} H↓n(t)\,dt/t$, and \α{Brent} has shown
that this can be written
$$\int ↑{1}↓{1/3} {G↓n(t)\over t}\,dt - \int ↑{1/3}↓{0}
{G↓n(t)\over 1 - t}\,dt + \sum ↓{k≥1}\,2↑{-k}\int↑{1/(1+2↑k)}↓{1/(1+2↑{k+1})}
{G↓n(t)\over t(1 - t)}\,dt.$$

\ansno 26. By induction, the length is
$m + \lfloor n/2\rfloor$ when $m ≥ n$, except that when $m =
n = 1$ there is {\sl no} path to $(0, 0)$.
% Vicinity of page 597
% folio 776 galley 6a 	*
\ansno 27. Let $a↓n = \biglp 2↑n - (-1)↑n\bigrp /3$; then $a↓0$,
$a↓1$, $a↓2$, $\ldots = 0$, 1, 1, 3, 5, 11, 21, $\ldotss\,$.\xskip (This sequence
of numbers has an interesting pattern of zeros and ones in its
binary representation. Note that $a↓n = a↓{n-1} + 2a↓{n-2}$,
and $a↓n + a↓{n+1} = 2↑n$.)\xskip For $m > n$, let $u = 2↑{m+1} -
a↓{n+2}$, $v = a↓{n+2}$. For $m = n > 0$, let $u = a↓{n+2}$ and $v
= 2a↓{n+1}$, or $u = 2a↓{n+1}$ and $v = a↓{n+2}$ (depending on which
is larger). Another example for the case $m = n > 0$ is $u = 2↑{n+1}
- 1$, $v = 2↑{n+1} - 2$; this choice takes more shifts, and gives $C
= n + 1$, $D = 2n$, $E = 1$.

\ansno 28. This is a problem where it appears to be necessary
to prove {\sl more} than was asked just to prove what was asked.
Let us prove the following: {\sl If $u$ and $v$ are positive integers,
Algorithm B does $≤1 + \lfloor\lg\max(u, v)\rfloor$ subtraction
steps; and if equality holds, then $\lfloor\lg (u
+ v)\rfloor > \lfloor\lg\max(u, v)\rfloor $.}

For convenience, let us assume that $u ≥ v$; let
$m = \lfloor\lg u\rfloor$, $n = \lfloor\lg v\rfloor$;
and let us use the ``lattice-point'' terminology, saying that
we are ``at point $(m, n)$.'' The proof is by induction on $m
+ n$.

\yskip{\sl Case 1}, $m = n$.\xskip Clearly, $\lfloor\lg(u
+ v)\rfloor > \lfloor\lg u\rfloor$ in this case. If $u =
v$ the result is trivial; otherwise the next subtraction-shift
cycle takes us to a point $(m - k, m)$. By induction, at most
$m + 1$ further subtraction steps will be required; but if $m
+ 1$ more {\sl are} needed, we have $\lfloor\lg\biglp (u -
v)2↑{-r} + v\bigrp \rfloor > \lfloor\lg v\rfloor$, where
$r ≥ 1$ is the number of right shifts that were made. This is
impossible, since $(u - v)2↑{-r} + v < (u - v) + v = u$. So
at most $m$ further steps are needed.

\yskip{\sl Case 2}, $m > n$.\xskip The next subtraction
step takes us to $(m - k, n)$, and at most $1 + \max(m - k, n)
≤ m$ further steps will be required. Now if $m$ further steps
{\sl are} required, then $u$ has been replaced by $u↑\prime
= (u - v)2↑{-r}$ for some $r ≥ 1$. By induction, $\lfloor\lg(u↑\prime
+ v)\rfloor ≥ m$; hence
$$\lfloor\lg(u + v)\rfloor = \lfloor\lg 2\biglp (u -
v)/2 + v\bigrp \rfloor ≥ \lfloor\lg 2(u↑\prime + v)\rfloor
≥ m + 1 > \lfloor\lg u\rfloor.$$

\ansno 29. Subtract the $k$th column from the $2k$th,
$3k$th, $4k$th, etc., for $k = 1$, 2, 3, $\ldotss\,$. The result
is a triangular matrix with $x↓k$ on the diagonal in column
$k$, where $m = \sum ↓{d\rslash m} x↓d$. It follows that $x↓m
= \varphi (m)$, so the determinant is $\varphi (1)\varphi (2)
\ldotsm \varphi (n)$.

[In general, ``\α{Smith}'s determinant,'' in
which the $(i, j)$ element is $f\biglp\gcd(i, j)\bigrp$ for
an arbitrary function $f$, is equal to $\prod↓{1≤m≤n} \sum ↓{d\rslash
m} \mu (m/d)f(d)$, by the same argument. See L. E. \α{Dickson},
{\sl History of the Theory of Numbers \bf 1} (New York: Chelsea,
1952), 122--123.]

\ansno 30. To determine $A$ and $r$ such that $u = Av + r$, $0
≤ r < v$, using ordinary long division, takes $O\biglp (1 +
\log A)(\log u)\bigrp$ units of time. If the quotients during
the algorithm are $A↓1$, $A↓2$, $\ldotss$, $A↓m$, then $A↓1A↓2 \ldotsm
A↓m ≤ u$, so $\log A↓1 +\cdots + \log A↓m ≤ \log
u$. Also $m = O(\log u)$.

\ansno 31. In general, since $(a↑u - 1)\mod (a↑v - 1) = a↑{u\mod v}
- 1$ (cf.\ Eq.\ 4.3.2--19), we find that $\gcd(a↑m - 1, a↑n - 1)
= a↑{\gcd(m,n)} - 1$ for all positive integers $a$.

\ansno 32. Yes, to $O\biglp n(\log n)↑2(\log
\log n)\bigrp$, even if we also need to compute the sequence of
partial quotients that would be computed by Euclid's algorithm;
see A. \α{Sch\"onhage}, {\sl Acta Informatica
\bf 1} (1971), 139--144.\xskip [But Algorithm L is better in practice
unless $n$ is extremely large.]

\ansno 34. Keep track of the most significant and least significant
words of the operands (the most significant is used to guess
the sign of $t$ and the least significant is to determine the
amount of right shift), while building a $2 \times 2$ matrix $A$ of
single-precision integers such that $A{u\choose v}={u↑\prime w\choose v↑\prime w}$,
where $w$ is the computer word size and
where $u↑\prime$ and $v↑\prime$ are smaller
than $u$ and $v$.\xskip (Instead of dividing the simulated odd operand
by 2, multiply the other one by 2, until obtaining multiples
of $w$ after exactly $\lg w$ shifts.)\xskip Experiments
show this algorithm running four times as fast as Algorithm
L\null, on at least one computer.

\ansno 35. (Solution by Michael \α{Penk}.)

\algstep Y1. [Find power of 2.] Same as step B1.

\algstep Y2. [Initialize.] Set $(u↓1,u↓2,u↓3)←(1,0,u)$ and
$(v↓1,v↓2,v↓3)←(v,1-u,v)$. If $u$ is odd, set $(t↓1,t↓2,t↓3)←(0,-1,-v)$ and
go to Y4. Otherwise set $(t↓1,t↓2,t↓3)←(1,0,u)$.

\algstep Y3. [Halve $t↓3$.] If $t↓1$ and $t↓2$ are both even, set
$(t↓1,t↓2,t↓3)←(t↓1,t↓2,t↓3)/2$; otherwise set $(t↓1,t↓2,t↓3)←(t↓1+v,t↓2-u,t↓3)/2
$.\xskip(In the latter case, $t↓1+v$ and $t↓2-u$ will both be even.)

\algstep Y4. [Is $t↓3$ even?] If $t↓3$ is even, go back to Y3.

\algstep Y5. [Reset $\max(u↓3,v↓3)$.] If $t↓3$ is positive,
set $(u↓1,u↓2,u↓3)←(t↓1,t↓2,t↓3)$;
otherwise set $(v↓1,v↓2,v↓3)←(v-t↓1,-u-t↓2,-t↓3)$.

\algstep Y6. [Subtract.] Set $(t↓1,t↓2,t↓3)←(u↓1,u↓2,u↓3)-(v↓1,v↓2,v↓3)$. Then
if $t↓1<0$, set $(t↓1,t↓2)←(t↓1+v,t↓2-u)$. If $t↓3≠0$, go back to B3. Otherwise
the algorithm terminates with $(u↓1,u↓2,u↓3\cdot2↑k)$ as the output.\quad\blackslug

\yyskip It is clear that the relations in (16) are preserved, and that $0≤u↓1,v↓1,
t↓1≤v$, $0≥u↓2,v↓2,t↓2≥-u$ after each of steps Y2--Y6. If $u$ is odd after step Y2,
then step Y3 can be simplified, since $t↓1$ and $t↓2$ are both even iff $t↓2$ is
even; similarly, if $v$ is odd, then $t↓1$ and $t↓2$ are both even iff $t↓1$ is
\inx{reciprocal modulo $m$}
even.  Thus, as in Algorithm X, it is possible to suppress all calculations
involving $u↓2$, $v↓2$, and $t↓2$, provided that $v$ is odd after step Y2. This
condition is often known in advance (e.g., when $v$ is prime and we are trying to
compute $u↑{-1}$ modulo $v$).
% Vicinity of page 599
% folio 777 galley 6b 	*
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)
\ansbegin{4.5.3}

\ansno 1. The running time is about
$19.02T + 6$, just a trifle slower than Program 4.5.2A.

\ansno 2. $\dispstyle\left({Q↓n(x↓1,x↓2,\ldotss ,x↓{n-1},x↓n)\atop Q↓{n-1}(x↓2,
\ldotss ,x↓{n-1},x↓n)}\9 {Q↓{n-1}(x↓1,x↓2, \ldotss , x↓{n-1})\atop Q↓{n-2}(x↓2,
\ldotss , x↓{n-1})}\right)$.

\ansno 3. $Q↓n(x↓1, \ldotss , x↓n)$.

\ansno 4. By induction, or by taking the determinant
of the matrix product in exercise 2.

\ansno 5. When the $x$'s are positive, the $q$'s
of (9) are positive, and $q↓{n+1} > q↓{n-1}$; hence (9) is an
alternating series of decreasing terms, and it converges iff
$q↓nq↓{n+1} → ∞$. By induction, if the $x$'s are greater
than $ε$, we have $q↓n ≥ c(1 + ε/2)↑n$, where $c$ is chosen small enough to make
this inequality valid for $n=1$ and 2. But if $x↓n = 1/2↑n$, we have $q↓n ≤ 2
- 1/2↑n$.

\ansno 6. It suffices to prove that $A↓1 = B↓1$;
and from the fact that $0 ≤ \bslash x↓1, \ldotss , x↓n\bslash
< 1$ whenever $x↓1, \ldotss , x↓n$ are positive integers, we
have $B↓1 = \lfloor 1/X\rfloor = A↓1$.

\ansno 7. Only $1\,2 \ldotsm n$ and $n \ldotsm 2\,1$.\xskip
(The variable $x↓k$ appears in exactly $F↓k\,F↓{n-k}$ terms; hence
$x↓1$ and $x↓n$ can only be permuted into $x↓1$ and $x↓n$. If
$x↓1$ and $x↓n$ are fixed by the permutation, it follows by
induction that $x↓2$, $\ldotss$, $x↓{n-1}$ are also fixed.)

\ansno 8. This is equivalent to
$${Q↓{n-2}(A↓{n-1}, \ldotss , A↓2) - XQ↓{n-1}(A↓{n-1}, \ldotss
, A↓1)\over Q↓{n-1}(A↓n, \ldotss , A↓2) - XQ↓n(A↓n, \ldotss ,
A↓1)} = -{1\over X↓n} ,$$
and by (6) this is equivalent to
$$X = {Q↓{n-1}(A↓2, \ldotss , A↓n) + X↓nQ↓{n-2}(A↓2, \ldotss
, A↓{n-1})\over Q↓n(A↓1, \ldotss , A↓n) + X↓nQ↓{n-1}(A↓1, \ldotss
, A↓{n-1})} .$$

\ansno 9. (a)\9 By definition.\xskip (b), (d) Prove this
when $n = 1$, then apply (a) to get the result for general $n$.\xskip
(c) Prove when $n = k + 1$, then apply (a).

\ansno 10. If $A↓0 > 0$, then $B↓0 = 0$, $B↓1 = A↓0$, $B↓2 = A↓1$,
$B↓3 = A↓2$, $B↓4 = A↓3$, $B↓5 = A↓4$, $m = 5$. If $A↓0 = 0$, then
$B↓0 = A↓1$, $B↓1 = A↓2$, $B↓2 = A↓3$, $B↓3 = A↓4$, $m = 3$. If $A↓0
= -1$ and $A↓1 = 1$, then $B↓0 = -(A↓2 + 2)$, $B↓1 = 1$, $B↓2 =
A↓3 - 1$, $B↓3 = A↓4$, $m = 3$. If $A↓0 = -1$ and $A↓1 > 1$,
then $B↓0 = -2$, $B↓2 = A↓1 - 2$, $B↓3 = A↓2$, $B↓4 = A↓3$, $B↓5 = A↓4$,
$m = 5$. If $A↓0 < -1$, then $B↓0 = -1$, $B↓1 = 1$, $B↓2 = -A↓0 -
2$, $B↓3 = 1$, $B↓4 = A↓1 - 1$, $B↓5 = A↓2$, $B↓6 = A↓3$, $B↓7 = A↓4$.\xskip
[Actually, the last three cases involve eight subcases; if any
of the $B$'s is set to zero, the values should be ``collapsed
together'' by using the rule of exercise 9(c). For example,
if $A↓0 = -1$, $A↓1 = A↓3 = 1$, we actually have $B↓0 = -(A↓2
+ 2)$, $B↓1 = A↓4 + 1$, $m = 1$. Double collapsing occurs when $A↓0
= -2$, $A↓1 = 1$.]
% Vicinity of page 600
% folio 777 galley 7 Bad beginning. 	*
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)
\ansno 11. Let $q↓n = Q↓n(A↓1, \ldotss , A↓n)$, $q↑\prime↓{n}
= Q↓n(B↓1, \ldotss , B↓n)$, $p↓n = Q↓{n+1}(A↓0, \ldotss , A↓n)$,
$p↑\prime↓{n} = Q↓{n+1}(B↓0, \ldotss , B↓n)$. By (5) and (11) we have $X =
{(p↓m + p↓{m-1}X↓m)/(q↓m + q↓{m-1}X↓m)}$, $Y = (p↑\prime↓{n}
+ p↑\prime↓{n-1}Y↓n)/\penalty0(q↑\prime↓{n} + q↑\prime↓{n-1}Y↓n)$;
therefore if $X↓m = Y↓n$, the stated relation between $X$ and
$Y$ holds by (8). Conversely, if $X = (qY + r)/(sY + t)$, $|qt
- rs| = 1$, we may assume that $s ≥ 0$, and we can show that
the partial quotients of $X$ and $Y$ eventually agree, by induction
on $s$. The result is clear when $s = 0$, by exercise 9(d).
If $s > 0$, let $q = as + s↑\prime$, where $0 ≤ s↑\prime < s$. Then
$X = a + 1/\biglp (sY + t)/(s↑\prime Y + r - at)\bigrp $; since
$s(r - at) - ts↑\prime = sr - tq$, and $s↑\prime < s$, we know
by induction and exercise 10 that the partial quotients of $X$
and $Y$ eventually agree.\xskip [{\sl Note:} The fact that $m$
is always odd in exercise 10 shows, by a close inspection of
this proof, that $X↓m=Y↓n$ if and only if $X=(qY+r)/(sY+t)$, where
$qt-rs=(-1)↑{m-n}$.]

\ansno 12. (a)\9 Since $V↓nV↓{n+1}=D-U↓{\!n}↑2$, we know that $D-U↓{\!n+1}↑2$ is
a multiple of $V↓{n+1}$; hence by induction $X↓n=(\sqrt D-U↓n)/V↓n$, where $U↓n$
and $V↓n$ are integers.\xskip
 [Note that the identity $V↓{n+1}=A↓n(U↓{n-1}-U↓n)+V↓{n-1}$
makes it unnecessary to divide when $V↓{n+1}$ is being determined.]

(b)\9 Let $Y=(-\sqrt D-U)/V$, $Y↓n=(-\sqrt D-U↓n)/V↓n$. The stated identity
obviously holds by replacing $\sqrt D$ by $-\sqrt D$ in the proof of (a). We have
$$Y=(p↓n/Y↓n+p↓{n-1})/(q↓n/Y↓n+q↓{n-1}),$$
where $p↓n$ and $q↓n$ are defined in part (c) of this exercise; hence
$$Y↓n=(-q↓n/q↓{n-1})(Y-p↓n/q↓n)/(Y-p↓{n-1}/q↓{n-1}).$$
But by (12), $p↓{n-1}/q↓{n-1}$ and $p↓n/q↓n$
are extremely close to $X$; since $X ≠ Y$, $Y - p↓n/q↓n$ and $Y
- p↓{n-1}/q↓{n-1}$ will have the same sign as $Y - X$ for all
large $n$. This proves that $Y↓n < 0$ for all large $n$; hence
$0 < X↓n < X↓n - Y↓n = 2\sqrt{D}/V↓n$; $V↓n$ must be positive.
Also $U↓n < \sqrt{D}$, since $X↓n > 0$. Hence $V↓n < 2\sqrt D$, since
$V↓n≤A↓nV↓n<\sqrt D+U↓{n-1}$.

Finally, we want to show that $U↓n>0$. Since $X↓n<1$, we have $U↓n>\sqrt D-V↓n$,
so we need only consider the case $V↓n>\sqrt D$; then $U↓n={A↓nV↓n-U↓{n-1}}≥
{V↓n-U↓{n-1}}>{\sqrt D-U↓{n-1}}$, and this is positive as we have already
observed.

{\sl Note:} In the repeating cycle, $\sqrt D+U↓n=A↓nV↓n+(\sqrt D-U↓{n-1})>
V↓n$; hence $\lfloor(\sqrt D+U↓{n+1})/V↓{n+1}\rfloor=\lfloor A↓{n+1}+V↓n/(\sqrt D
+U↓n)\rfloor=A↓{n+1}=\lfloor(\sqrt D+U↓n)/V↓{n+1}\rfloor$. 
In other words $A↓{n+1}$ is
determined by $U↓{n+1}$ and $V↓{n+1}$; we can determine $(U↓n,V↓n)$ from its
successor $(U↓{n+1},V↓{n+1})$ in the period. In fact, when $0<V↓n<\sqrt D+U↓n$ and
$0<U↓n<\sqrt D$, the arguments above prove that $0<V↓{n+1}<\sqrt D+U↓{n+1}$ and
$0<U↓{n+1}<\sqrt D\,$; moreover, if the pair $(U↓{n+1},V↓{n+1})$ follows $(U↑\prime,
V↑\prime)$ with $0<V↑\prime<\sqrt D+U↑\prime$ and $0<U↑\prime<\sqrt D$, then
$U↑\prime=U↓n$ and $V↑\prime=V↓n$. Hence {\sl$(U↓n,V↓n)$ is part of the cycle
if and only if\/\ $0<V↓n<\sqrt D+U↓n$ and\/\ $0<U↓n<\sqrt D$.}

\yyskip (c) $\dispstyle{-V↓{n+1}\over V↓n} = X↓nY↓n
 = {(q↓nX - p↓n)(q↓nY - p↓n)\over
(q↓{n-1}X - p↓{n-1})(q↓{n-1}Y - p↓{n-1})}.$

\yyskip\noindent There is also a companion identity, namely
$$Vp↓np↓{n-1} + U(p↓nq↓{n-1} + p↓{n-1}q↓n) + \biglp (U↑2 -
D)/V\bigrp q↓nq↓{n-1} = (-1)↑nU↓n.$$

(d)\9 If $X↓n = X↓m$ for some $n ≠ m$, then $X$
is an irrational number that satisfies the quadratic equation
$(q↓nX - p↓n)/(q↓{n-1}X - p↓{n-1}) = (q↓mX - p↓m)/(q↓{m-1}X -
p↓{m-1})$.

\ansno 14. As in exercise 9, we need only verify the stated
identities when $c$ is the last partial quotient, and this verification
is trivial. Now Hurwitz's rule gives $2/e = \bslash 1, 2, 1,
2, 0, 1, 1, 1, 1, 1, 0, 2, 3, 2, 0, 1, 1, 3, 1, 1, 0, 2, 5,
\ldotss\bslash $. Taking the reciprocal, collapsing out the
zeros as in exercise 9, and taking note of the pattern that
appears, we find (cf.\ exercise 16) that $e/2 = 1 + \bslash\,
2, \overline{2m + 1, 3, 1, 2m + 1, 1, 3}\bslash$, $m ≥ 0$.\xskip [{\sl Schriften der
phys.-\"okon.\ Gesellschaft zu K\"onigsberg \bf 32}
(1891), 59--62.]

\ansno 15. $\biglp$This procedure maintains
four integers $(A, B, C, D)$ with the invariant meaning that
``our remaining job is to output the continued fraction for
$(Ay + B)/(Cy + D)$, where $y$ is the input yet to come.''$\bigrp$\xskip
Initially set $j ← k ← 0$, $(A, B, C, D) ← (a, b, c, d)$; then
input $x↓j$ and set $(A, B, C, D) ← (Ax↓j + B, A, Cx↓j + D,
C)$, $j ← j + 1$, one or more times until $C + D$ has the same
sign as↔$C$.\xskip $\biglp$When $j ≥ 1$ and the input has not terminated,
we know that $1 < y < ∞$; and when $C + D$ has the same sign
as↔$C$ we know therefore that $(Ay + B)/(Cy + D)$ lies between
$(A + B)/(C + D)$ and $A/C$.$\bigrp$\xskip Now comes the general step:
If no integer lies strictly between $(A + B)/(C + D)$ and $A/C$,
output $X↓k ← \lfloor A/C\rfloor $, and set $(A, B, C, D) ←
(C, D, A - X↓kC, B - X↓kD)$, $k ← k + 1$; otherwise input $x↓j$
and set $(A, B, C, D) ← (Ax↓j + B, A, Cx↓j + D, C)$, $j ← j +
1$. The general step is repeated ad infinitum. However, if at
any time the {\sl final\/} $x↓j$ is input, the algorithm immediately
switches gears: It outputs the continued fraction for $(Ax↓j
+ B)/(Cx↓j + D)$, using Euclid's algorithm, and terminates.

The following tableau shows the working for the
requested example, where the matrix $\biglp{B\atop D}\,{A\atop C}\bigrp$
begins at the upper left corner, then shifts right one on
input, down one on output:
$$\vbox{\baselineskip0pt\lineskip0pt
\def\\{\vrule depth 2.5pt height 8.5pt}
\def\¬{\vrule height 3pt}
\halign{\hfill#⊗\hbox to 24.2pt{$\hfill#$\9}⊗#⊗\!
\hbox to 30pt{$\hfill#$\9}⊗\!
\hbox to 30pt{$\hfill#$\9}⊗\!
\hbox to 30pt{$\hfill#$\9}⊗\!
\hbox to 30pt{$\hfill#$\9}⊗\!
\hbox to 30pt{$\hfill#$\9}⊗\!
\hbox to 30pt{$\hfill#$\9}⊗\!
\hbox to 30pt{$\hfill#$\9}⊗\!
\hbox to 30pt{$\hfill#$\9}⊗\!
\hbox to 30pt{$\hfill#$\9}⊗\!
\hbox to 34.6pt{$\hfill#$\quad}⊗#\cr
\noalign{\moveright 25pt\hbox to 305pt{\leaders\hrule\hfill}}
⊗⊗\¬⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗\¬\cr
⊗⊗\\⊗x↓j⊗-1⊗5⊗1⊗1⊗1⊗2⊗1⊗2⊗∞⊗\\\cr
⊗⊗\¬⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗\¬\cr
\noalign{\hrule}
\¬⊗⊗\¬⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗\¬\cr
\\⊗X↓k⊗\\⊗39⊗97⊗-58⊗-193⊗⊗⊗⊗⊗⊗⊗\\\cr
\\⊗-2⊗\\⊗-25⊗-62⊗37⊗123⊗⊗⊗⊗⊗⊗⊗\\\cr
\\⊗2⊗\\⊗⊗⊗16⊗53⊗⊗⊗⊗⊗⊗⊗\\\cr
\\⊗3⊗\\⊗⊗⊗5⊗17⊗22⊗⊗⊗⊗⊗⊗\\\cr
\\⊗7⊗\\⊗⊗⊗1⊗2⊗3⊗5⊗⊗⊗⊗⊗\\\cr
\\⊗1⊗\\⊗⊗⊗⊗3⊗1⊗4⊗5⊗14⊗⊗⊗\\\cr
\\⊗1⊗\\⊗⊗⊗⊗⊗2⊗1⊗3⊗7⊗⊗⊗\\\cr
\\⊗1⊗\\⊗⊗⊗⊗⊗⊗⊗2⊗7⊗9⊗25⊗\\\cr
\\⊗12⊗\\⊗⊗⊗⊗⊗⊗⊗1⊗0⊗1⊗2⊗\\\cr
\\⊗2⊗\\⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗1⊗\\\cr
\\⊗∞⊗\\⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗0⊗\\\cr
\¬⊗⊗\¬⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗\¬\cr}
\hrule}$$
M. \α{Mend\`es France} has shown
that the number of quotients output per quotient input is asymptotically
bounded between $1/r$ and $r$, where $r = 2\lfloor K(|ad - bc|)/2\rfloor
+ 1$ and $K$ is the function defined in exercise 38; this bound
is best possible.\xskip [{\sl Topics in Number Theory}, ed.\ by P. \α{Tur\'an},
{\sl Colloquia Math. Soc. J\'anos Bolyai \bf13} (1976), 183--194.]

\α{Gosper} has also shown that the
above algorithm can be generalized to compute
the continued fraction for $(axy + bx + cy + d)/(Axy + Bx +
Cy + D)$ from those of $x$ and $y$ (in particular, to compute
\inx{addition of continued fractions}
sums and products).\xskip
[MIT AI Laboratory Memo 239 (Feb.\ 29, 1972), Hack 101.]
% Vicinity of page 602
% folio 781 galley 8 	*
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)
\ansno 16. It is not difficult to prove by induction that $f↓n(z)
= z/(2n + 1) + O(z↑3)$ is an odd function with a convergent
power series in a neighborhood of the origin, and that it satisfies
the given differential equation. Hence
$$f↓0(z) = \bslash z↑{-1} + f↓1(z)\bslash = \cdots = \bslash
z↑{-1}, 3z↑{-1}, \ldotss , (2n + 1)z↑{-1} + f↓{n+1}(z)\bslash.$$
It remains to prove that $\lim↓{n→∞}\bslash z↑{-1},
3z↑{-1}, \ldotss , (2n + 1)z↑{-1}\bslash = f↓0(z)$.\xskip [Actually
\α{Euler}, age 24, obtained continued fraction expansions for the
considerably more general differential equation $f↑\prime↓{\!n}(z)
= az↑m + bf↓n(z)z↑{m-1} + cf↓n(z)↑2$; but he did not bother
to prove convergence, since formal manipulation and intuition
were good enough in the eighteenth century.]

There are several ways to prove the desired limiting
equation. First, letting $f↓n(z) = \sum ↓k a↓{nk}z↑k$, we can
argue from the equation
$$\twoline{(2n + 1)a↓{n1} + (2n + 3)a↓{n3}z↑2 + (2n + 5)a↓{n5}z↑4
+\cdots}{0pt}{= 1 - (a↓{n1}z + a↓{n3}z↑3 + a↓{n5}z↑5 +\cdotss)↑2}$$
that $(-1)↑ka↓{n(2k+1)}$ is a sum of terms of
the form $c↓k/(2n + 1)↑{k+1}(2n + b↓{k1}) \ldotsm (2n + b↓{kk})$,
where the $c↓k$ and $b↓{km}$ are positive integers independent
of $n$. For example, we have $-a↓{n7} = 4/(2n + 1)↑4(2n + 3)(2n + 5)(2n
+ 7) + 1/(2n + 1)↑4(2n + 3)↑2(2n + 7)$. Thus $|a↓{(n+1)k}| ≤
|a↓{nk}|$, and $|f↓n(z)| ≤ \tan |z|$ for $|z| < π/2$. This
uniform bound on $f↓n(z)$ makes the convergence proof very simple.
Careful study of this argument reveals that the power series
for $f↓n(z)$ actually converges for $|z| < π\sqrt{2n + 1}/2$;
this is interesting, since it shows that the singularities of
$f↓n(z)$ get farther and farther away from the origin as $n$
grows, so the continued fraction actually represents $\hbox{tanh}\,z$
{\sl throughout} the complex plane.

Another proof gives further information of a different
kind: If we let
$$A↓n(z) = n! \sum ↓{0≤k≤n}{2n-k\choose n}\,z↑k/k!
= \sum ↓{k≥0} {(n + k)!\,z↑{n-k}\over k!\,(n - k)!} ,$$
then
$$\eqalign{A↓{n+1}(z)⊗= \sum ↓{k≥0} {(n + k - 1)!\,\biglp (4n + 2)k +
(n + 1 - k)(n - k)\bigrp\over k!\,(n + 1 - k)!}\,z↑
{n+1-k}\cr⊗= (4n + 2)A↓n(z)+ z↑2A↓{n-1}(z).\cr}$$
It follows, by induction, that
$$\baselineskip29pt
\eqalign{Q↓n\left({1\over z}, {3\over z} , \ldotss , {2n - 1\over z}\right)
⊗ = {A↓n(2z) + A↓n(-2z)\over 2↑{n+1}z↑n},\cr
Q↓{n-1}\left({3\over z} , \ldotss , {2n - 1\over z}\right) ⊗= {A↓n(2z)
- A↓n(-2z)\over 2↑{n+1}z↑n} .\cr}$$
Hence
$$\bslash z↑{-1}, 3z↑{-1}, \ldotss , (2n - 1)z↑{-1}\bslash
= {A↓n(2z) - A↓n(-2z)\over A↓n(2z) + A↓n(-2z)} ,$$
and we want to show that this ratio approaches
$\hbox{tanh}\,z$. By Eqs.\ 1.2.9--11 and 1.2.6--24,
$$e↑zA↓n(-z) = n! \sum ↓{m≥0} z↑m\,\biggglp \sum
↓{0≤k≤n} {m\choose k}{2n - k\choose n}(-1)↑k\,\bigggrp
=\sum ↓{m≥0}{2n - m\choose n}\,z↑m\,{n!\over m!}.$$
Hence
$$e↑zA↓n(-z) - A↓n(z) = R↓n(z) = (-1)↑nx↑{2n+1} \sum ↓{k≥0}
{(n + k)!\,x↑k\over (2n + k + 1)!\,k!} .$$
We now have $(e↑{2z} - 1)\biglp A↓n(2z)
+ A↓n(-2z)\bigrp - (e↑{2z} + 1)\biglp A↓n(2z) - A↓n(-2z)\bigrp
= 2R↓n(2z)$; hence
$$\hbox{tanh}\,z-\bslash z↑{-1}, 3z↑{-1}, \ldotss , (2n - 1)z↑{-1}\bslash
= {2R↓n(2z)\over \biglp A↓n(2z) + A↓n(-2z)\bigrp (e↑{2z} + 1)}.$$
Thus we have an exact formula for the
difference. When $|z| ≤ 1$, the factor $e↑{2z} + 1$ is bounded away
from zero, $|R↓n(2z)| ≤ e\,n!/(2n + 1)!$, and
$$\eqalign{\textstyle{1\over2}|A↓n(2z)+A↓n(-2z)|
⊗≥n!\,\biggglp{2n\choose n}-{2n-2\choose n}
-{2n-4\choose n}-\cdots\bigggrp\cr
\noalign{\vskip3pt}
⊗≥ {(2n)!\over n!}{\textstyle(1 - {1\over 4} - {1\over
16} -\cdotss)}= {2\over 3} {(2n)!\over n!}.\cr}$$
Thus convergence is very rapid, even for complex values of $z$.

To go from this continued fraction to the continued
fraction for $e↑z$, we have $\hbox{tanh}\,z = 1 - 2/(e↑{2z} + 1)$; hence
we get the continued-fraction representation for $(e↑{2z} +
1)/2$ by simple manipulations. Hurwitz's rule gives the expansion
of $e↑{2z} + 1$, from which we may subtract unity. For $n$ odd,
$$e↑{-2/n} = \bslash\,\overline{1, 3mn + \lfloor n/2\rfloor
, (12m + 6)n, (3m + 2)n + \lfloor n/2\rfloor , 1}\bslash ,\qquad
m ≥ 0.$$

Another derivation has been given by C. S. \α{Davis},
{\sl J. London Math.\ Soc.\ \bf 20} (1945), 194--198.

\ansno 17. (b)\9 $\bslash x↓1 - 1, 1, x↓2
- 2, 1, x↓3 - 2, 1, \ldotss , 1, x↓{2n-1} - 2, 1, x↓{2n} - 1\bslash
$.\xskip[{\sl Note:} One can remove negative parameters from \α{continuants}
by using the identity
$$\twoline{Q↓{m+n+1}(x↓1,\ldotss,x↓n,-x,y↓m,\ldotss,y↓1)=}{3pt}{
(-1)↑{m-1}Q↓{m+n+2}(x↓1,\ldotss,
x↓{n-1},x↓n-1,1,x-1,-y↓m,\ldotss,-y↓1),}$$
from which we obtain
$$\twoline{Q↓{m+n+1}(x↓1,\ldotss,x↓n,-x,y↓m,\ldotss,y↓1)=}{3pt}{
-Q↓{m+n+3}(x↓1,\ldotss,x↓{n-1},x↓n-1,1,x-2,1,y↓m-1,y↓{m-1},\ldotss,y↓1)}$$
after a second application.]

(c)\9
$1 + \bslash 1, 1, 3, 1, 5, 1,\ldotss\bslash=1+\bslash\overline{2m+1,1}\bslash$,
\quad $m≥0$.

\ansno 19. The sum for $1 ≤ k ≤ N$ is $\log↓b \biglp (1+x)(N+1)/(N+1+x)\bigrp$.

\ansno 20. Let $H = SG$, $g(x) = (1 + x)G↑\prime
(x)$, $h(x) = (1 + x)H↑\prime (x)$. Then (35) implies that $h(x
+ 1)/(x + 2) - h(x)/(x + 1) = -(1 + x)↑{-2}g\biglp1/(1 +x)\bigrp
/\biglp 1 + 1/(1 + x)\bigrp $.

\ansno 21. $\varphi (x) = c/(cx + 1)↑2 + (2 - c)/\biglp (c -
1)x + 1\bigrp ↑2$, $U\varphi (x) = 1/(x + c)↑2$. When $c ≤ 1$,
the minimum of $\varphi (x)/U\varphi (x)$ occurs at $x = 0$
and is $2c↑2 ≤ 2$. When $c ≥ \phi = {1\over 2}(\sqrt{5} + 1)$,
the minimum occurs at $x = 1$ and is $≤\phi ↑2$. When $c \approx
1.31266$ the values at $x = 0$ and $x = 1$ are nearly equal
and the minimum is $>3.2$; the bounds $(0.29)↑n\varphi ≤ U↑n\varphi
≤ (0.31)↑n\varphi$ are obtained. Still better bounds come from well-chosen
linear combinations $Tg(x) = \sum a↓j/(x + c↓j)$.

\ansno 23. By the interpolation formula of exercise 4.6.4--15
with $x↓0 = 0$, $x↓1 = x$, $x↓2 = x + ε$, letting $ε → 0$, we have
the general identity $R↑\prime↓{n}(x) = \biglp R↓n(x) - R↓n(0)\bigrp
/x + {1\over 2}xR↓n↑{\prime\prime}\biglp \theta (x)\bigrp$ for some $\theta
(x)$ between 0 and $x$, whenever $R↓n$ is a function with continuous
second derivative. Hence in this case $R↑\prime↓{n}(x) =
O(2↑{-n})$.

\ansno 24. $∞$.\xskip [A. \α{Khinchin}, in {\sl Compos.\ Math.\ \bf 1} (1935),
361--382, proved that the sum $A↓1 +\cdots + A↓n$
of the first $n$ partial quotients of a real number $X$ will
be asymptotically $n\lg n$, for almost all $X$. Exercise 35 shows that the behavior
is different for rational↔$X$.]
% Vicinity of page 604
% folio 784 galley 9 	*
\def\bslash{\char'477 } \def\vbslash{\char'477017 } % boldface slashes (vol. 2 only)
\ansno 25. Any union of intervals can be written as a union
of disjoint intervals, since we have
$\lower7pt\null\union↓{k≥1} I↓k = \union↓{k≥1}\biglp I↓k \rslash
\union↓{1≤j<k}
I↓j\bigrp$, and this is a disjoint union in which $I↓k\rslash\union↓{1≤j<k}
I↓j$ can be expressed as a finite union of disjoint intervals.
Therefore we may take $\Iscr = \union I↓k$, where $I↓k$ is an interval
of length $ε/2↑k$ containing the $k$th rational number in $[0,
1]$, using some enumeration of the rationals. In this case $\mu(
\Iscr)≤ ε$, but $\|\Iscr∩ P↓n\| = n$ for all $n$.

\ansno 26. The continued fractions $\bslash A↓1, \ldotss , A↓t\bslash$
that appear are precisely those for which ${A↓1 > 1}$, ${A↓t > 1}$,
and $Q↓t(A↓1, A↓2, \ldotss , A↓t)$ is a divisor of $n$. Therefore
(6) completes the proof.\xskip [{\sl Note:} If $m↓1/n
= \bslash A↓1, \ldotss , A↓t\bslash$ and $m↓2/n = \bslash
A↓t, \ldotss , A↓1\bslash $, where $m↓1$ and $m↓2$ are relatively
prime to $n$, then $m↓1m↓2 ≡ \pm 1\modulo n$; this rule
defines the correspondence. When $A↓1 = 1$ an analogous symmetry
is valid, according to (44).]

\ansno 27. First prove the result for
$n = p↑e$, then for $n = rs$, where $r$ and $s$ are relatively
prime. Alternatively, use the formulas in the next exercise.

\ansno 28. (a)\9 The left-hand side is multiplicative
(see exercise 1.2.4--31), and it is easily evaluated when $n$
is a power of a prime.\xskip (c) From (a), we have {\sl \α{M\"obius's
inversion formula}\/}: If $f(n) = \sum ↓{d\rslash n} g(d)$,
then $g(n) = \sum ↓{d\rslash n} \mu (n/d)f(d)$.

\ansno 29. The sum is approximately $\biglp\biglp(12\ln 2)/π↑2\bigrp\ln N!\bigrp/N
- \sum ↓{d≥1}\Lambda(d)/d↑2 + 1.47$; here $\sum ↓{d≥1}\Lambda
(d)/d↑2$ converges to the constant value $-\zeta ↑\prime
(2)/\zeta (2)$, and we know that $\ln N! = N \ln N - N + O(\log N)$ by
Stirling's approximation.

\ansno 30. The modified algorithm affects the calculation if
and only if the following division step in the unmodified algorithm
would have the quotient 1, and in this case it avoids the following
division step. The probability that a given division step is
avoided is the probability that $A↓k = 1$ and that this quotient
is preceded by an even number of quotients equal to 1. By the
symmetry condition, this is the probability that $A↓k = 1$ and
is {\sl followed} by an even number of quotients equal to 1.
The latter happens if and only if $X↓{k-1} > \phi - 1 = 0.618
\ldotss $, where $\phi$ is the golden ratio: For $A↓k = 1$ and $A↓{k+1}
>1$ iff ${2\over 3} ≤ X↓{k-1} < 1$; $A↓k = A↓{k+1} = A↓{k+2}
= 1$ and $A↓{k+3} > 1$ iff ${5\over 8} ≤ X↓{k-1} < {2\over 3}$;
etc. Thus we save approximately $F↓{k-1}(1) - F↓{k-1}(\phi -
1) \approx 1 - \lg \phi \approx 0.306$ of the division steps.
The average number of steps is approximately $\biglp(12\ln \phi)/π↑2\bigrp\ln
n$, when $v = n$ and $u$ is relatively prime to $n$. \α{Kronecker}
[{\sl Vorlesungen \"uber Zahlentheorie \bf 1} (Leipzig:
Teubner, 1901), 118] observed that this choice of least remainder
in absolute value always gives the shortest possible number
of iterations, over all algorithms that replace $u$ by $(\pm
u)\mod v$ at each iteration. For further results see N. G.
\α{de Bruijn} and W. M. \α{Zaring}, {\sl Nieuw Archief voor Wiskunde
\rm(3) \bf 1} (1953), 105--112; G. J. \α{Rieger}, {\sl Math.\ Nachr.\
\bf 82} (1978), 157--180.

On many computers, the modified algorithm makes
each division step longer; the idea of exercise 1, which saves
{\sl all} division steps when the quotient is unity, would be
preferable in such cases.

\ansno 31. Let $a↓0 = 0$, $a↓1 = 1$, $a↓{n+1} = 2a↓n + a↓{n-1}$;
then $a↓n = \biglp (1 + \sqrt{2})↑n - (1 - \sqrt{2})↑n\bigrp
/2\sqrt{2}$, and the worst case (in the sense of Theorem F)
occurs when $u = a↓n + a↓{n-1}$, $v = a↓n$, $n ≥ 2$.

This result is due to A. \α{Dupr\'e} [{\sl
J. de Math.\ \bf 11} (1846), 41--64], who also investigated more
general ``look-ahead'' procedures suggested by J. \α{Binet}. See
P. \α{Bachmann}, {\sl Niedere Zahlentheorie \bf 1} (Leipzig: Teubner,
1902), 99--118, for a discussion of early analyses of Euclid's
algorithm.

\ansno 32. (b)\9 $Q↓{m-1}(x↓1, \ldotss , x↓{m-1})Q↓{n-1}(x↓{m+2}, \ldotss
, x↓{m+n})$ corresponds to Morse code sequences of length $(m
+ n)$ in which a dash occupies positions $m$ and $(m + 1)$;
the other term corresponds to the opposite case.\xskip (Alternatively,
use exercise 2. The more general identity
$$\baselineskip14pt
\twoline{Q↓{m+n}(x↓1, \ldotss , x↓{m+n})Q↓k(x↓{m+1}, \ldotss , x↓{m+k})
=}{3pt}{\lpile{Q↓{m+k}(x↓1, \ldotss , x↓{m+k})Q↓n(x↓{m+1}, \ldotss , x↓{m+n})\cr
\quad\null+ (-1)↑kQ↓{m-1}(x↓1, \ldotss , x↓{m-1})Q↓{n-k-1}(x↓{m+k+2}, \ldotss
, x↓{m+n})\cr}}$$ also appeared in Euler's paper.)

\ansno 33. (a)\9 The new representations are $x = m/d$, $y = (n
- m)/d$, $x↑\prime = y↑\prime = d = \gcd(m, n - m)$, for ${1\over
2}n < m < n$.\xskip (b) The relation $(n/x↑\prime ) - y ≤ x < n/x↑\prime$
defines↔$x$.\xskip (c) Count the $x↑\prime$ satisfying (b).\xskip (d) A
pair of integers $x > y > 0$ with ${\gcd(x, y)= 1}$ can be uniquely
written in the form $x = Q↓m(x↓1, \ldotss , x↓m)$, $y = Q↓{m-1}(x↓1,
\ldotss , x↓{m-1})$, where ${x↓1 ≥ 2}$ and ${m ≥ 1}$; here $y/x = \bslash
x↓m, \ldotss , x↓1\bslash $.\xskip (e) It suffices to show that $\sum
↓{1≤k≤n/2}T(k, n) = 2\lfloor n/2\rfloor + h(n)$. For $1 ≤ k
≤ n/2$ the continued fractions $k/n = \bslash x↓1, \ldotss ,
x↓m\bslash$ run through all sequences $(x↓1,\ldotss,x↓m)$ such that
$m≥1$, $x↓1≥2$, $x↓m≥2$, $Q↓m(x↓1,\ldotss,x↓m)\rslash n$; and $T(k,n)=2 + (m - 1)$.

\baselineskip 12pt
\ansno 34. (a)\9 Dividing $x$ and $y$ by $\gcd(x,
y)$ yields $g(n) = \sum ↓{d\rslash n} h(n/d)$; apply exercise
28(c), and use the symmetry between primed and unprimed variables.\xskip
(b) For fixed $y$ and↔$t$, the representations with $xd ≥ x↑\prime$
have $x↑\prime < \sqrt{nd}$; hence there are $O(\sqrt{nd}/y)$
such representations. Now sum for $0 < t ≤ y < \sqrt{n/d}$.\xskip
(c) If $s(y)$ is the given sum, then $\sum ↓{d\rslash y} s(d)
= y(H↓{2y} - H↓y) = k(y)$, say; hence $s(y) = \sum ↓{d\rslash
y} k(y/d)$. Now $k(y) = y \ln 2 - {1\over 4} + O(1/y)$.\xskip (d)
$\sum ↓{1≤y≤n} \varphi (y)/y↑2 = \sum ↓{1≤y≤n,\,d\rslash y} \mu
(d)/yd = \sum ↓{cd≤n} \mu (d)/cd↑2$.\xskip $\biglp$Similarly, $\sum ↓{1≤y≤n}
\sigma ↓{-1}(y)/y↑2 = O(1).\bigrp$\xskip (e) $\sum ↓{1≤k≤n} \mu (k)/k↑2
= 6/π↑2 + O(1/n)$ $\biglp$see exercise 4.5.2--10(d)$\bigrp$; and $\sum ↓{1≤k≤n}
\mu (k)\log k/k↑2 = O(1)$. Hence we have $h↓d(n) = n\biglp(3 \ln 2)/π↑2\bigrp
\ln(n/d) + O(n)$ for $d ≥ 1$. Finally $h(n) = 2 \sum ↓{cd\rslash
n} \mu (d)h↓c(n/cd) = \biglp (6 \ln 2)/π↑2\bigrp n\biglp \ln n -
\sum - \sum ↑\prime \bigrp+ O\biglp n\sigma ↓{-1}(n)↑2\bigrp $, where
the remaining sums are
$\sum = \sum ↓{cd\rslash n} \mu (d)\ln(cd)/cd = 0$ and $\sum
↑\prime = \sum ↓{cd\rslash n} \mu (d)\ln c/cd = \sum ↓{d\rslash
n}\Lambda(d)/d$.\xskip [It is well known that $\sigma ↓{-1}(n) =
O(\log\log n)$; cf.\ \α{Hardy} and \α{Wright}, {\sl Theory of Numbers},
$\section$22.9.]

\baselineskip 11pt
\ansno 35. See {\sl Proc.\ Nat.\ Acad.\ Sci.\ \bf72} (1975), 4720--4722.

\ansno 36. Working the algorithm backwards, we
want to choose $k↓1$, $\ldotss$, $k↓{n-1}$ so that $u↓k ≡ F↓{k↓1}
\ldotsm F↓{k↓{i-1}}F↓{k↓i}-1$
$\biglp$modulo $\gcd(u↓{i+1}, \ldotss , u↓n)\bigrp$ for $1 ≤i< n$, with
$u↓n = F↓{k↓1} \ldotsm F↓{k↓{n-1}}$ a
minimum, where the $k$'s are positive, $k↓1 ≥ 3$, and $k↓1 +\cdots
+ k↓{n-1} = N + n - 1$. The solution is $k↓2 =\cdots
= k↓{n-1} = 2$, $u↓n = F↓{N-n+3}$.\xskip [See {\sl CACM
\bf 13} (1970), 433--436, 447--448.]

\ansno 37. See {\sl Proc.\ Amer.\ Math.\
Soc.\ \bf 7} (1956), 1014--1021; cf.\ also exercise 6.1--18.

\ansno 38. Let $m = \lceil n/\phi \rceil $, so that $m/n = \phi
↑{-1} + ε = \bslash x↓1, x↓2, \ldotss \bslash$ where $0 < ε
< 1/n$. Let $k$ be minimal such that $x↓k ≥ 2$; then $\biglp
\phi ↑{1-k} + (-1)↑kF↓{k-1}ε\bigrp\hbox{\:a/}\biglp \phi ↑{-k} - (-1)↑kF↓kε\bigrp
≥ 2$, hence $k$ is even and $\phi ↑{-2} = 2 - \phi ≤ \phi ↑kF↓{k+2}ε
= (\phi ↑{2k+2} - \phi ↑{-2})ε/\sqrt{5}$.\xskip [{\sl Ann.\ Polon.\ Math.\
\bf 1} (1954), 203--206.]

\ansno 39. At least 287 at bats; $\bslash
\,2, 1, 95\bslash = 96/287 = .33449477 \ldotss$, and no fraction
with denominator $<287$ lies in the interval $[.3335, .3345] = [\bslash\, 2,
1, 666\bslash ,\, \bslash\, 2, 1, 94, 1, 1, 3\bslash ]$.

To solve the general question of the fraction
in $[a, b]$ with smallest denominator, where $0 < a < b < 1$,
note that in terms of regular continued-fraction representations
\inx{comparison of continued fractions}
we have $\bslash x↓1, x↓2,\ldotss\bslash < \bslash y↓1, y↓2,
\ldotss\bslash$ iff $(-1)↑jx↓j<(-1)↑jy↓j$ for the smallest $j$ with $x↓j
≠ y↓j$, where we place ``$∞$'' after the last partial quotient
of a rational number. Thus if $a = \bslash x↓1, x↓2,\ldotss\bslash$
and $b = \bslash y↓1, y↓2,\ldotss\bslash $, and if $j$ is minimal with
$x↓j≠y↓j$, the fractions in
$[a, b]$ have the form $c = \bslash x↓1, \ldotss , x↓{j-1},
z↓j, \ldotss , z↓m\bslash$ where $\bslash z↓j, \ldotss , z↓m\bslash$
lies between $\bslash x↓j, x↓{j+1},\ldotss\bslash$ and $\bslash
y↓j, y↓{j+1},\ldotss\bslash$ inclusive. Let $Q↓{-1} = 0$. The
denominator $$Q↓{j-1}(x↓1, \ldotss , x↓{j-1})Q↓{m-j+1}(z↓j, \ldotss
, z↓m) + Q↓{j-2}(x↓1, \ldotss , x↓{j-2})Q↓{m-j}(z↓{j+1}, \ldotss
, z↓m)$$ of $c$ is minimized when $m = j$ and $z↓j = (j$ odd
$\→ y↓j + 1 - \delta ↓{y↓{j+1}∞};\,x↓j+1-\delta↓{x↓{j+1}∞})$.\xskip
[Another way to derive this method comes from the theory in the
following exercise.]

\ansno 40. One can prove by induction that $p↓rq↓l-p↓lq↓r=1$ at each node,
hence $p↓l$ and $q↓l$ are relatively prime. Since $p/q<p↑\prime/q↑\prime$
implies that $p/q<(p+p↑\prime)/(q+q↑\prime)<p↑\prime/q↑\prime$, it is
also clear that the labels on all left descendants of $p/q$ are less than
$p/q$, while the labels on all its right descendants are greater. Therefore
each rational number occurs at most once as a label.

It remains to show that each rational does appear. If $p/q=\bslash a↓1,
\ldotss,a↓r,1\bslash$, where each $a↓i$ is a positive integer, one can show
by induction that the node labeled $p/q$ is found by going left $a↓1$ times, then
right $a↓2$ times, then left $a↓3$ times, etc.

[The sequence of labels on successive levels of this tree was first studied by
M.↔A. \α{Stern}, {\sl J. f\"ur die reine und Angew.\ Math.\ \bf55} (1858),
193--220, although the relation to binary trees is not explicit in his paper.
\α{Peirce} independently
communicated this construction in a letter dated July 17, 1903, but
he never published it; and during the next few years he occasionally
amused himself by making rather cryptic remarks about it without revealing the
underlying mechanism. See C. S. Peirce, {\sl The New Elements of Mathematics
\bf3} (The Hague: Mouton, 1976), 781--784, 826--829; also {\bf1}, 207--211;
and his {\sl Collected Papers \bf4} (1933), 276--280. See also D. H. \α{Lehmer},
{\sl AMM \bf36} (1929), 59--67.]

\ansno 41. In fact, the regular continued fractions for numbers of the general form
$${1\over l↓1}+{(-1)↑{e↓1}\over l↓1↑2l↓2}+{(-1)↑{e↓2}\over l↓1↑4l↓2↑2l↓3}+\cdots$$
have an interesting pattern, based on the \α{continuant} identity
$$\baselineskip14pt
\twoline{Q↓{m+n+1}(x↓1,\ldotss,x↓{n-1},x↓n-1,1,y↓m-1,y↓{m-1},\ldotss,y↓1)=
}{3pt}{\lpile{x↓nQ↓{n-1}(x↓1,\ldotss,x↓{n-1})Q↓m(y↓m,\ldotss,y↓1)\cr
\quad\null+(-1)↑m
Q↓{m+n}(x↓1,\ldotss,x↓{n-1},0,-y↓m,-y↓{m-1},\ldotss,-y↓1).\cr}}$$
This identity is most interesting when $y↓m=x↓{n-1}$, $y↓{m-1}=x↓{n-2}$, etc., since
$$Q↓{n+1}(z↓1,\ldotss,z↓k,0,z↓{k+1},\ldotss,z↓n)=Q↓{n-1}(z↓1,\ldotss,z↓{k-1},
z↓k+z↓{k+1},z↓{k+2},\ldotss,z↓n).$$ In particular we find that if $p↓n/q↓n=
Q↓{n-1}(x↓2,\ldotss,x↓n)/Q↓n(x↓1,\ldotss,x↓n)=\bslash x↓1,\ldotss, x↓n\bslash$,
then $p↓n/q↓n+(-1)↑n/q↓n↑2r=\bslash x↓1,\ldotss,x↓n,r-1,1,x↓n-1,x↓{n-1},\ldotss,
x↓1\bslash$. By changing $\bslash x↓1,\ldotss,x↓n\bslash$ to $\bslash x↓1,\ldotss,
x↓{n-1},x↓n-1,1\bslash$, we can control the sign $(-1)↑n$ as desired.

For example, the partial sums of the first series have the following continued
fractions of even length: $\bslash 1,1\bslash$; $\bslash 1,1,1,1,0,1\bslash=
\bslash1,1,1,2\bslash$; $\bslash1,1,1,2,1,1,1,1,1,1\bslash$;
$\bslash1,1,1,2,1,1,1,1,1,1,1,1,0,1,1,1,1,1,2,1,1,1\bslash=
\bslash1,1,1,2,1,1,1,1,1,1,1,2,1,1,1$, $1,2,1,1,1\bslash$; and from this point on
the sequence settles down and obeys a simple reflecting pattern. We find that
the $n$th partial quotient $a↓n$ can be computed rapidly as follows, if
$n-1=20q+r$ where $0≤r<20$:
$$a↓n=\left\{\,\vcenter{\baselineskip 14pt\halign{$#,\hfill$\quad⊗if $r=#\hfill\cr
1⊗0,2,4,5,6,7,9,10,12,13,14,15,17$ or 19;\cr
2⊗3$ or 16;\cr
1+(q+r)\mod2⊗8$ or 11;\cr
2-d↓q⊗1$;\cr
1+d↓{q+1}⊗18$.\cr}}\right.$$
Here $d↓n$ is the ``\α{dragon sequence}'' defined by the rules $d↓0=1$, $d↓{2n}=d↓n$,
$d↓{4n+1}=0$, $d↓{4n+3}=1$; the \α{dragon curve} discussed in exercise 4.1--18
turns right at its $n$th step iff $d↓n=1$.

Liouville's numbers with $l≥3$ are equal to $\bslash l-1$, $l+1$, $l↑2-1$, 1,
$l$, $l-1$, $l↑{12}-1$, 1, $l-2$, $l$, 1, $l↑2-1$, $l+1$, $l-1$, $l↑{72}-1$,
$\ldotss\bslash$. The $n$th partial quotient $a↓n$ depends on the dragon sequence
on $m\mod4$ as follows: If $n\mod4=1$ it is $l-2+d↓{n-1}+\biglp\lfloor n/2\rfloor
\mod4\bigrp$ and if $n\mod4=2$ it is $l+2-d↓{n+2}-\biglp\lfloor n/2\rfloor\mod4\bigrp$;
if $n\mod4=0$ it is 1 or $l↑{k!(k-1)}-1$, depending on whether or not $d↓n=0$ or
1, where $k$ is the largest power of↔2 dividing↔$n$; and if $n\mod4=3$ it is
$l↑{k!(k-1)}-1$ or 1, depending on whether $d↓{n+1}=0$ or 1, where $k$ is the
largest power of↔2 dividing↔${n+1}$. When $l=2$ the same rules apply, except that
0's must be removed, so there is a more complicated pattern depending on
$n\mod24$.

[Cf.\ {\sl J. Number Theory \bf11} (1979), 209--217.]
\end % be sure this comes at an opportune time!